문제
동네 편의점의 주인인 동빈이는 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 |
풀이
- 답안
n = int(input())
data = list(map(int, input().split()))
data.sort()
target = 1
for x in data:
# 만들 수 없는 금액을 찾았을 때 반복 종료
if target < x:
break
target += x
# 만들 수 없는 금액 출력
print(target)
아이디어
- 동전을 화폐 단위 기준으로 정렬(오름차순)한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 1부터 차례대로 특정한 금액을 만들 수 있는지 확인해 target 변수를 업데이트하는 방법으로 최적의 해를 계산.
- 현재 상태를 '1부터 target - 1까지의 모든 금액을 만들 수 있는 상태'라고 하고 이때 매번 target인 금액도 만들 수 있는지(현재 확인하는 동전의 단위(x)가 target 이하인지) 체크하는 것. 만약 해당 금액을 만들 수 있다면(x <= target) target의 값을 업데이트(현재 상태를 업데이트_ target += x)하면 된다.
출처: 나동빈, 「이것이 취업을 위한 코딩테스트다 with 파이썬」, 한빛미디어, p.314
'Algorithms > 이코테' 카테고리의 다른 글
[구현] 왕실의 나이트 (0) | 2023.07.29 |
---|---|
[Greedy] 이코테 - 볼링공 고르기(py) (1) | 2023.07.11 |
[Greedy] 이코테 - 문자열 뒤집기(py) (0) | 2023.07.11 |
[Greedy] 이코테 - 곱하기 혹은 더하기(py) (0) | 2023.07.11 |
[Greedy] 이코테 - 모험가 길드(py) (0) | 2023.07.09 |