이것이 코딩테스트다 - 3)그리디

 

 

원래대로라면 알고리즘 문제해결 전략책 2권을 완료했어야 하지만 😭

내 기본 개념이 너무나도 부족한 관계로 조금더 설명이 자세하고 쉬운 책으로 재구매를 했는데

그게 바로 '이것이 코딩테스트다'이다.

 

유튜브에 강의도 올라와있고, 기본개념부터 설명해주고 문제난이도도 종만북보다는 괜찮은 것 같아서 구매했다!

 

빠른시일내에 끝내고 알고리즘 문제해결 전략책도 끝내보자! 아자아자!

 

 

3.1) 거스름 돈

#include <iostream>

using namespace std;

int main() {
	int n, cnt = 0, money[4] = { 500, 100, 50, 10 };

	cin >> n;

	for (int i = 0; i < 4; i++)
	{
		if (n == 0) break;
		cnt += n / money[i];
		n %= money[i];
	}

	cout << cnt << endl;
	return 0;
}

 

 

3.2)큰 수의 법칙

#include<iostream>
#include <algorithm>

using namespace std;

int main() {

	int n, m, k, number[10000], cnt = 0, answer=0;

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
	{
		cin >> number[i];
	}

	sort(number.begin(), number.end(),compare);//내림차순 정렬

	cnt = m / (k + 1) * k + m % (k + 1);
	answer += cnt * number[0];
	answer += (m - cnt) * second;

	/*
	* 처음에 짰던 코드
	1.
	while (m>0)
	{
		if (cnt == k)
		{
			cnt = 0;
			answer += number[1];
			m--;
		}
		else
		{
			cnt++;
			answer += number[0];
			m--;
		}
	}
	2.
	while (1)
	{
		for (int i = 0; i < k; i++)
		{
			if (m == 0) break;
			answer += number[0];
			m--;
		}
		if (m == 0) break;
		answer += number[1];
		m--;
	}
	*/

	cout << answer << endl;
	return 0;
}

 

 

 

3.3) 숫자 카드 게임

#include <iostream>

int main() {

	int n, m, result, min_value;

	for (int i = 0; i < n; i++)
	{
		min_value = 10001;
		for (int j = 0; j < m; j++)
		{
			int x; 
			cin >> x;
			min_value = min(min_value, x);
		}

		result = max(min_value, result);
	}
	
	cout << result << endl;
	
	
	
	/* 
	óÀ½ Ç®¾ú´ø ¹æ¹ý
	int n, m, card[100][100], LowNum[100], Min=2147000000;
	for (int i = 0; i < n; i++)
	{
		Min = 2147000000;
		for (int j = 0; j < m; j++)
		{
			cin >> card[i][j];
			if (card[i][j] < Min)
				Min = card[i][j];
		}
		LowNum[i] = Min;
	}
	int Max =-1;
	for (int i = 0; i < n; i++)
	{
		if (LowNum[i] > Max)
			Max = LowNump[i];
	}
	cout << Max << endl;
	*/

	return 0;

}

 

 

3.4) 1이 될 때 까지

(순수하게 문제를 따라가기 보다 코드를 간단하고 짧게 짜는 연습이 많이 필요하다!)

#include <iostream>


int main() {
	int n, k,cnt;
	cin >> n >> k;

	while (1)
	{
		int target = (n / k) * k;
		cnt += (n - target);
		n = target;
		if (n < k) break;
		cnt += 1;
		n /= k;
	}
	cnt += (n - 1);
	cout << cnt << endl;


	/*óÀ½¿¡ Çß´ø ¹æ¹ý
	while (n >= k)
	{
		while (n % k != 0)
		{
			n -= 1;
			cnt++;
		}
		n /= k;
		cnt++;		
	}
	while (n > 1)
	{
		n--;
		cnt++;
	}
	cout << cnt << endl;
	*/

	return 0;
}