(유형별 기출/그리디) 만들 수 없는 금액

만들 수 없는 금액

동네 편의점의 주인인 동빈이는 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 이하의 자연수입니다.

출력조건

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

입력

5
3 2 1 1 9

출력

8

---

풀이

음...일단 만들 수 없는 수중에 가장 작은 수를 구하는거니까 1부터 검증을 시작해야한다는 생각에서 시작하였다.

그럼 1이 만들 수 있을 지 없을지는 어떻게 알수 있을까

우선 입력 값 중에 같은 수 가 있으면 만들 수 있는 수가 되므로 이를 먼저 검증한다.

없을 경우... 어떻게 검증하지? 라는 생각에서 나아가지 못했다.

 

나중에 풀이를 보고 나서야 알게 되었는데 이건 어느정도 비슷한 문제를 풀어 형식을 암기하는 문제같았다. 예를 들면 풀수는 있지만 하루걸리는 문제를 식을 알면 몇초 걸리는 풀이로 풀어낼 수 있는 문제를 본 기분이랄까..?

사실 이 식이란 것도 처음에는 이해하기 조금 어려울 수 있다. 하지만 같이 이 문제를 풀고 있는 그대여! 좌절하지말자

 

그래서 설명을 해보자면 이 문제는 target이라는 변수를 사용한다. target은 쉽게 말하자면 이 수까지는 만들수 있는 수라는 일종의 보증이다. 

동전[1, 2, 3, 5, 13]이 있다고 해보자. 먼저 target을 1부터 올려본다고 하자. 동전 1 이 있으므로 target==1은 증면될 수 있다. 그러면 target은 2(1+1)이 된다. 1까지는 만들 수 있다고 증명하였기때문이다. 동전2가 있기때문에 이도 증명된다. 그러면 target은 4(2+2)가 된다. target값을 만들기 위해 target값보다 작은 동전3 값이 있기때문에 이 또한 증명되어 다음 atrget값은 7(4+3)이 된다. 이런식으로 진행되는 과정이다.

혹시 글을 읽고 이해가 되지않는다면 

https://kk-programming.tistory.com/11 

[이코테-그리디] 기출 - 04. 만들 수 없는 금액

위의 블로그에서 제공하는 표를 참고해보기를 추천한다. 나도 이를 보고서야 이해하기 시작했다.

그래서 과정은 

i = 0부터 i++

1.target = 1, s[i]이 1이면 target+=s[i]로 갱신, i++, 아니면 1을 반환

2.만약 target >= s[i]이면 target+=s[i]로 갱신, i++, 아니면 target을 반환

...반복...

 

---

코드

n = int(input())
coin = list(map(int, input().split()))
coin.sort()
target = 1
for i in range(n):
    if target>=coin[i]:
        target += coin[i]
    else:
        print(target)