[그리디/python] 만들 수 없는 금액 (정답, 내 해석 및 풀이)

문제

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.
예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.
또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

 

정답

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

 

풀이

예전에 몇 시간을 풀다가 도저히 모르겠어서 답지를 봤더니

일차적으로 정답코드가 너무 간단해 놀랐고 

이차로 풀이를 봐도 원리가 이해가 안가서 더 혼란스러웠던 문제..

 

어떻게든 이해해보고자 인터넷에 올라온 온갖 블로그 글과 풀이를 다 뒤졌는데도 처음엔 이해하지 못해서 많이 답답했다.

포기하고 있다가 코테감각을 살리기 위해 최근 다시 풀면서 결국 어느정도 이해하기 성공...

 

 

문제를 풀기 위해 가장 핵심적인 두 가지 원리를 알아보자

 

1. n원을 만들 수 있는지 확인하고자 할 때(=target), (n-1)까지는 만들 수 있는 것으로 가정한다.

처음엔 이게 이해가 안됐음. 어떻게 n-1까지 만들 수 있다고 확신하지? 

이유는 어찌보면 당연하게도 우리는 타겟을 1부터 시작해 1씩 증가시켜가며 만들 수 있는지 확인할텐데,

만약 n-1까지의 수 중 만들 수 없는 수가 있었다면 그게 답이었겠지

 

2. n원을 만들 수 있을 때, 다음 동전으로 k원이 들어온다면 n원부터 (n+k)원까지 추가로 만들 수 있다.

예를들어서 내가 가진 동전들을 어찌어찌 조합해서 1원부터 4원까지는 만들 수 있다고 가정해보자. 

다음 5원을 만들 수 있는지를 확인해야하는데 (target = 5)

이 때, 다음 동전으로 3원이 들어왔다면 새로운 동전 3원에 가지고 있는 동전을 조합해 1~4원까지의 동전을 각각 더하면

3

3 + 1 = 4

3 + 2 = 5

3 + 3 = 6

3 + 4 = 7

이렇게 5~7까지를 추가적으로 만들 수 있다.(3,4는 이미 만들 수 있으므로 제외)

그래서 총 (1~4), (5~7)까지, 즉 1부터 7까지의 의 동전을 만들 수 있게 됨.

 

다른 예시를 보자

마찬가지로 4까지는 만들 수 있다고 치고 다음 동전으로 6원이 들어왔다면

새로운 동전 6원에 가지고 있는 동전을 잘 조합해(1~4)까지의 동전을 각각 더해

6

6 + 1 = 7

6 + 2 = 8

6 + 3 = 9

6 + 4 = 10

이렇게 6~10까지를 추가적으로 만들 수 있게 된다.

그래서 총 (1~4), (6~10)까지의 동전을 만들 수 있게 된다. 하지만 5를 만들 수 없다.

 

첫 번째 예시에서는 1부터 7까지의 빈 숫자 없이 다 만들 수 있었지만 

두 번째 예시에서는 중간에 5가 빠져 있는 것을 확인할 수 있다. 

 

이를 통해 알 수 있는 점은

새로들어온 동전의 금액이 타겟금액보다 크다면

타겟금액을 만들 수 없다는 것이다.

 

 

정리하자면,
타겟금액을 1씩 증가시켜가며 만들 수 있는지 여부를 확인할텐데, 
1. 새로 들어오는 코인이 타겟금액보다 같거나 작아야지만 타겟금액을 만들 수 있다
2. 만들 수 있다면 다음 타켓금액을 새로 업데이트 해야하는데 위 예시를 통해 일일이 1씩 증가시킬 필요 없고
(만들 수 있는 금액 + 새로 들어온 코인) 만큼 만들 수 있음을 알고 있다. 그러므로 다음 타겟을
(이전 타겟 + 새로 들어온 코인) 으로 갱신해주면 될 것이다.

 

 

이해를 했다고 생각하는 지금도 

이 문제를 나중에 다시 만나면 풀 수 있을지 확신을 못할 정도로 나에겐 어려웠떤 문제..

그리디를 얼마나 풀어야 이런 문제를 쉽게 풀 수 있을까,, ㅜ

 

 

 

참조

이것이 취업을 위한 코딩테스트다(with. python)