[ 이것이 코딩테스트다 ] 만들 수 없는 금액 - 그리디 알고리즘

[  이것이 취업을 위한 코딩테스트다 with 파이썬  ] 만들 수 없는 금액 _ Python 파이썬

 

" 문제 "

 

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

 

<입력 조건>

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. ( 1 <= N <= 1000 )

둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.

 

<출력 조건>

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

 

입력예시	출력예시
5 3 2 1 1 9	8

 

---

" 아이디어 "

주어진 동전 리스트를 오름차순으로 sort() 하고

맨 처음 동전부터 차례대로 동전을 추가해가며 만들 수 없는 금액을 찾는 방식으로 풀이하면 된다.

 

예를들면,

현재 동전리스트가 1, 1, 2 라면 만들 수 있는 금액은 1~4 원이다.

(쉬운 이해를 위해 이미 루프를 돌아 동전 3개를 추가한 이후라고 가정하였다.)

그 다음 확인해야할 금액 target은 5이다.

 

전체 동전 리스트가 [1, 1, 2, 2]와 [1, 1, 2, 6] 인경우를 비교해보자.

 

(1) [1, 1, 2, 2]

 

이미 1~4인 금액은 만들 수 있으므로 새로 추가할  2 원짜리 동전으로는

 

1 + 2 = 3

2 + 2 = 4

...

4 + 2 = 6

 

까지 만들 수 있다.

그러므로 기존 target에 새 동전의 단위를 더하여

target += 2  를 하여 증가시킨다.

그러면 현재 target은 7이 된다.

더이상 추가할 동전이 없으므로

만들 수 없는 최소금액은 7이다.

 

(2) [1, 1, 2, 6]

 

이미 1~4인 금액은 만들 수 있으므로 새로 추가할 6원짜리 동전으로는

 

1 + 6 = 7

...

4 + 6 = 10

 

까지 만들 수 있다.

이 경우 문제가 있다.

target보다 새로 추가한 동전의 금액이 크다는 점이다.

6원짜리 동전은 단위가 너무 커서 5, 6 을 건너 뛰게된다.

그래서 이 경우, 만들 수 없는 최소금액은 5이다.

 

이렇게 새로운 동전이 추가되었을 때 이전  target+ 새 동전의 금액 을 하면서 target를 올려나가면 되고,

target보다 새 동전의 단위가 큰 경우 현재 target이 만들 수 없는 금액이 된다. 

 

아래 표를 보면 target이 어떻게 증가하는지 확인할 수 있다.

 

 

target (확인하고자 하는 금액)	새로 추가된 동전	현재 동전 리스트	만들 수 있는 금액
1	1	[ 1 ]	1
1 + 1 = 2	1	[ 1, 1 ]	1~2
2 + 1 = 3	2	[ 1, 1, 2 ]	1~4
3 + 2 = 5	6	[ 1, 1, 2, 6 ]	1~4 / 7~10 (5, 6이 빠짐)

 

---

" 코드 "

 

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

---

" 참고자료 "