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

[문제]

동네 편의점의 주인인 동빈이는 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
32119

<출력 예시>
8

 

---

[책 풀이]

🔎 이해 과정

책의 아이디어는 다음과 같다.

• 동전의 화폐 단위를 오름 차순 정렬한다.
• 1부터 차례대로 단계를 거쳐 특정한 금액(target)을 만들 수 있는지 확인한다.
• 1부터 특정한 target-1까지의 모든 금액을 만들 수 있다고 가정해보자
• 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target금액 또한 만들 수 있는지 확인한다. 
• 여기서 현재 확인하는 동전금액이 target보다 이하여야 그 동전을 이용하여 target을 만들 수 있다.
• 만약 해당 target 금액을 만들 수 있다면 target의 값을 업데이트한다.

 

그럼 target 값은 어떤식으로 업데이트 할까?
현재 확인하는 동전을 이용해서 target 금액을 만들 수 있는 조건이 무엇일까?

다음 예를 보자 

동전 [1, 2, 3, 5, 13] 이 있다. target 값을 1원 부터 1씩 증가시키고, 작은 금액의 동전부터 하나씩 추가하면서 target의 금액들을 만들 수 있는지 확인해보자. 초기 target값은 1이다.

3단계에서 우리는 이전 단계에서 3원(초기 target값 -1) 까지 만들 수 있는 것을 안다. 이 상태에서 3원(새로 추가되는 동전 금액)을 추가하여 4원(초기 target값)을 만들 수 있는 지 확인한다.

이때 4원(초기 target값)이 3원(새로 추가되는 동전 금액)보다 크기 때문에 3원(새로 추가되는 동전 금액)을 이용해서 4원(초기 target값)을 만들 수 있다.

그리고 우리는 추가된 동전 3원을 이용해 3(이전 단계에서 만들 수 있는 금액)+3(추가된 동전 금액) = 6원까지 만들 수 있다는 것을 안다.

따라서 초기 target 값이 새로 추가되는 동전 금액보다 작다는 것이 확인되면,

(이전 단계에서 만들 수 있는 금액) + (추가 되는 동전 금액) 까지 당연히 만들 수 있다. 

그리고 우리는 새로운 동전을 추가하면서 다음 단계로 넘어가게 되는데, 여기서 다음 단계에서 확인해야하는 초기 target값은 (이전 단계 초기 target값) + (이전 단계에서 추가된 동전 금액)이다.

단계 4에서도 위 설명과 동일하게 11원까지 만들 수 있다는 것이 확인되고, 단계 5에서는 확인하는 초기 target값 12가 추가된 동전 금액 13보다 작기 때문에 12원은 만들 수 없게 된다.

(동전 [1, 2, 3, 5]만 있을 때는 11원까지만 만들 수 있고, 12원보다 큰 13원과 이전 단계 조합들로 12원을 만들 수 없기 때문이다.)

따라서 우리는 각 단계의 초기 target값이 추가되는 동전보다 큰지 작은지만 확인하면 된다. 크다면 추가되는 동전으로 그 target값을 만들 수있고, 작다면 만들 수 없다. 

즉

• 동전을 오름차순으로 정렬한다.
• 동전을 한개씩 추가하면서, target 값을 1부터 추가되는 동전금액을 합하면서 증가시킨다.
• 추가된 동전 금액이 target 값보다 작거나 같아야 추가된 동전 금액을 이용하여 그 target 값을 만들 수 있다.
• 추가된 동전 금액이 target 값보다 크다면 그 target 값이 만들 수 없는 최소 금액이다.

따라서 우리는 위의 표를 아래와 같이 간략히 할 수 있다. 

step	target 값	현재 coin	target을 만들 수 있는지 여부
0	새 동전으로 금액 1을 만들 수 있는지 확인해야하므로 초기 target 값은 1이다.
1	1	[1]	O (1==1)
2	2	[1, 2]	O (2==2)
3	4	[1, 2, 3]	O (4 > 3)
4	7	[1, 2, 3, 5]	O (7 > 5)
5	12	[1, 2, 3, 5, 13]	X (12 < 13)

 

🔎 코드

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)

 

---

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬

* 포스팅에 책의 내용과 개인적인 해석이 같이 포함됩니다.