[C/C++] 나동빈 만들 수 없는 금액, Greedy

문제

동빈이는 N개의 동전을 가지고 있다. N개의 동전의 단위(1,000,000이하의 자연수)를 입력받고, 이 N개의 동전을 조합하여 만들 수 없는 정수 중 최솟값을 구하라. 예를 들어 N=5이고 각 단위가 3, 2, 1, 1, 9일 때 만들 수 없는 정수의 최소 단위는 8이다.  (N은 1,000보다 작거나 같은 자연수)

코드

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main() {
	vector<int> coin;
	int N, num, result=1;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		coin.push_back(num);
	}
	sort(coin.begin(), coin.end());

	num = 1;
	while (1) {
		for (int i = N - 1; i > -1; i--)
			if (coin[i] <= num) 
				num -= coin[i];
		if (num == 0)
			num = ++result;
		else
			break;
	}
	cout << result;
}

풀이

1. 숫자를 증가시켜가며 비교할 변수 num과 result=1를 선언한다.

2. 입력받은 동전들을 오름차순으로 정렬하고, for문을 사용해 가장 높은 동전 단위부터 num과 비교한다.

3. coin[i]번째 값이 num보다 작거나 같으면 num-=coin[i]

4. coin[i]번째 값이 num보다 크다면 그 다음으로 큰 동전 단위로 넘어간다

5. for문이 끝났을 때 num=0이면 입력받은 동전들로 조합이 가능한 수이므로, result의 값을 증가시켜 num에 저장한다.

6. num값이 0이 아니라면 입력받은 동전들로 조합이 불가능한 것이므로, num을 출력하고 종료한다.