[탐욕법] 난이도1, K 대회 기출 '만들 수 없는 금액' (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 이하의 자연수입니다.

<출력 조건>

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

---

<문제 풀이>

1. 처음에 결과값을 1로 지정하고 각 동전을 더한다.

2. 만약 다음 동전이 결과값보다 크다면, 결과값 반환

 

<코드>

#220321
from itertools import combinations

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

result = {i:0 for i in range(1,1000000+1)}

for i in range(1,n+1):
    tmp = set(combinations(money, i))
    for j in tmp:
        result[sum(j)] += 1

print(sorted(result.items(), key=lambda x:x[1])[0][0])

#이취코 답

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)

 

<고쳐야 할 점>

• 최대한 효율적인 방법 생각하기
• 복습 알고리즘