[이코테 / C++] 만들 수 없는 금액

greedy

문제 설명

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.

또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

입력

• 첫 째줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1≤N≤1,000)

• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.

출력

• 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

내 코드

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

using namespace std;

int main(void)
{
	int N;
	scanf("%d",&N);

	int nums[N];
	for(int i=0;i<N;i++)
		scanf("%d",&nums[i]);

	sort(nums,nums+N);

	int target = 1;
	for(int i=0;i<N;i++){
		if(target < nums[i])
			break;
		target += nums[i];
	}
	printf("%d\n",target);
    return 0;
}

배울 점

target을 1부터 올려가면서 1 ~ (target-1) 까지의 범위는 이미 만들 수 있다는 것이 보장된다는 아이디어