[그리디] 만들 수 없는 금액

N 개의 동전을 가지고 있고, 화폐 단위는 1,000,000 이하의 자연수다. 이때 N 개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구해라.

 

예를 들어 N = 5이고 각 동전이 3원, 2원, 1원, 1원, 9원 이라면 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.

또 다른 예로 N = 3이고 각 동전이 3원, 5원, 7원 이라면 답은 1원이다.

 

문제를 보고 처음든 생각은 이랬다. 가능한 모든 수를 Set으로 저장해놓고 1부터 1,000,000 까지 for문 돌려서 없는 숫자가 나오면 답인것으로. 그런데 모든 수를 구하기 위한 방식이 마땅치 않았다.

 

답 코드를 보면 먼저 정렬 한 후에, 구해야 되는 target 숫자를 차례차례 체크하는 방식으로 이루어져 있다.

예를 들어 data 가 [1,2,3,8] 이라고 했을 때(정렬 후), target 은 1부터 시작하고 for문을 돌면서 index에 해당하는 숫자를 계속 더해간다.

즉, target은 최초 1에서 2가 됐다가 4, 7 순서로 증가하다 7이 8보다 작으므로 for문이 끝나고 7이 답이 된다(증가할 때마다 index 에 해당하는 숫자가 더 커지게 되면 target을 못구하는 것으로 판단되어 답이 된다).

 

결국 이 문제의 핵심은 정렬과 target 증가 원리의 이해다. 리스트로 주어진 숫자들을 부분집합 개념으로 다 더해보지 않고도 구할 수 있다는걸 알기 때문에(이게 가능하려면 정렬이 전제되어야 함), target 값과 index에 해당하는 값을 더한다.

N = input()
data = list(map(int, input().split()))
data.sort()
target = 1

for i in data:
	if target < i:
		break

	target += i

print(target)

 

출처 : 이것이 코딩테스트다 나동빈 저