[Python] 이것이 코딩테스트다 with 파이썬 - 만들 수 없는 금액 - 그리디 알고리즘

해당 문제 및 해설은 "이것이 코딩테스트 다 with 파이썬" 책을 기준으로 요약 및 정리하여 작성하였습니다.

 

이것은 코딩테스트다 with 파이썬 구입처

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

---

문제

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

 

내 코드 - 조합을 사용,  테스트 케이스 통과

from itertools import combinations

n = int(input())
data = list(map(int, input().split()))

arr_sum = []

# n 이 1 일 때
for i in data:
  arr_sum.append(i)

# n 이 2 이상일 때
for i in range(2, n + 1):
  arr = list(combinations(data, i))
  for i in arr:
    arr_sum.append(sum(i))

result = 1

while True:
  if result not in arr_sum:
    break
  result += 1
  
print(result)

 

답안 코드 - 책, 테스트 케이스 통과

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)