[이것이 코딩테스트다] 만들 수 없는 금액

문제

첫번쨰 입력줄엔 1에서 1000까지의 동전의 갯수가 n이 주어진다.

두번째줄에는 n개의 동전의 화폐 단위를 나타내는 숫자가 차례 대로 들어온다.

 

출력으로 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.

 

입력 예시

5

3 2 1 1 9

 

출력

8

 

해결 방법

 

전형적인 정렬 그리디 문제입니당.

만들 수 없는 숫자를 찾을 떄까지 target을 업데이트한다.

예를 들어 3 2 1 1 9 의 입력이 들어오면 정렬한 1 1 2 3 9인데,

target이 1일 때, 입력 숫자 중의 1이 있으니 만들 수 있기 때문에 target을 1+1 =2 로 업데이트

target이 2일 때 입력 숫자 중 1이 두개로 만들 수 있으므로 target을 2+1=3로 업데이트

target 3일 때, 입력 숫자 중 2와 1로 만들 수 있으므로 target을 2+3=5로 업데이트

target 5일 때, 입력숫자 3과 2로 만들 수 있으므로 target을 5+3=8로 업데이트

target 8일 때, 만들 수 없으므로 정답은 8

 

이런식으로 target을 업데이트하며 만들 수 없을 때까지 업데이트해서 확인해준다.

 

코드

n=map(int,input())
coin=list(map(int, input().split()))

coin=sorted(coin, reverse=True)

minval=1
for x in coin :
    if minval <x :
        break
    else :
        minval+=x
answer=minval
print(answer)

 

※<이것이 취업을 위한 코딩테스트다(나동빈 저)>를 참고하여 작성되었습니다.