[그리디] 이코테 (파이썬) 만들 수 없는 금액 풀이

[문제]

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수

 

금액 중 최솟값을 구하는 프로그램을 작성하세요.

 

예를 들어, N = 5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다.

 

이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.

 

또 다른 예시로, N = 3이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위_ 동전이라고 가정합시다.

 

이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

 

[입력 조건]

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

 

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

 

[출력 조건]

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

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

 

[풀이]

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

target = 1
for i in arr :
  # 만들 수 없는 금액을 찾았을 때 반복 종료
  if target < i :
    break
  target += i

print(target)

 

각 동전의 화폐 단위를 나타내는 n개의 자연수를 입력받고 오름차순으로 정렬하여 반복문을 통해 하나씩 확인한다.

 

만약 target 값이 현재의 동전 화폐 단위보다 작을 경우 만들 수 없는 금액이기 때문에 반복문을 빠져나와

 

그 값을 출력하고 프로그램을 종료한다.

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저