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

---

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

 

2023.12.06 - [Algorithm] - [이코테] 02. 그리디(Greedy) 알고리즘, 탐욕법, 욕심쟁이 알고리즘

[이코테] 02. 그리디(Greedy) 알고리즘, 탐욕법, 욕심쟁이 알고리즘

---

문제

편의점 주인은 N개의 동전을 가지고 있다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하라

 

입력 조건

• 첫째 줄에 동전의 개수를 나타내는 양의 정수 N이 주어진다. (1 ≤ N ≤ 1,000)
• 둘째 줄에 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분된다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수이다.

출력 조건

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

 

입력 예시
5
3 2 1 1 9

출력 예시
8

 

---

해설

정렬을 이용한 그리디 알고리즘으로 해결할 수 있다.

1. 동전을 화폐 단위를 기준으로 오름차순 정렬한다.
2. 이후에 1부터 차례대로 특정한 금액을 만들 수 있는지 확인한다.

• 1부터 target-1 까지의 모든 금액을 만들 수 있을 때, target 금액 또한 만들 수 있는지 확인한다.
• 만약 target 금액을 만들 수 있다면, target 값을 증가시킨다.

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

target = 1
for x in arr:
    # 만들 수 없다면 종료
    if target < x:
        break
    target += x

print(target)

---