(그리디) 이것이 코딩테스트다 11장 Q4 _ 만들 수 없는 금액 [Python]

[문제]

• 동네 편의점의 주인인 동빈이는 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)

문제의 출력 조건인 3, 2, 1, 1, 9로 생각해보자.

 

우선 주어진 입력을 정렬해 1 1 2 3 9로 만들어준다.

 

그 후 target이란 변수를 만들어 어떤 금액까지 주어진 동전들로 만들 수 있는지 계속 업데이트한다.

(이때, target - 1까지 만들 수 있는 것이다.)

 

target < x 라면, 즉 target보다 큰 x가 존재한다면 더 이상 진행해봤자 더 큰 금액들만 남았을 것이므로 반복문을 멈춘다.

 

그게 아니라면 target = target + x를 반복적으로 진행해 target의 크기를 계속 키워준다.

 

최종적으로 출력하는 것은 만들 수 없는 금액의 최소값이므로 target - 1이 아닌 target을 출력해준다.