[알고리즘 일기] 157. 만들 수 없는 금액

문제 157. (2022-01-19)

이코테 그리디 기출문제 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
3 2 1 1 9

 

❧ 출력 예시

8

---

❧ 정답

🔑 그리디 알고리즘) 현재 동전리스트로 만들 수 없는 값 중 최솟값 출력

동전 화폐 단위를 담아두는 rst를 집합으로 설정해서, 이후에 동일한 값을 받았을 때 중복으로 저장되지 않게 한다.

| Ex) 4(3+1)와 4(2+2)를 중복 처리하지 않게 하기 위함

 

for 문을 돌면서 각 동전 1개로 합을 만드는 경우 부터 N개로 만드는 경우까지 모든 경우의 수를 구해서 rst에 해당 값을 각각 저장한다.

 

rst를 오름차순으로 정렬한 뒤, rst에 있는 값들에서 양의 정수 최솟값을 구한다.
rst의 마지막 원소까지 도달했을 때, 최솟값이 도출되지 않는다면 맨 마지막 값에 +1한 값을 출력한다.

 

| Ex)

# 입력 예시
3
1 2 2

-> 이 경우 위의 알고리즘을 적용했을 때 rst에 들어가는 값들 : 1(1), 2(2), 3(1+2), 4(2+2), 5(1+2+2)
이럴 경우 양의 정수 최솟값은 6이 된다.

 

✏️ combinations 라이브러리를 사용해서 현재 숫자들로 합을 구할 수 있는 모든 조합을 구한다.