만들 수 없는 금액 그리드

N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예제 N=5 3,2,1,1,9 동전을 가지고 있을때 양의 정수 금액중 최솟값은 8

N=3 3,5,7원 최솟값은 1

가장먼저 드는 생각은 조합을 통해서 리스트를 뽑고 조건을 만족하지 못하는 가장 작은 값을 취하면 되나 했지만 이는 번거롭게 느껴졌다.

from itertools import combinations

num = int(input())
num_list = list(map(int,input().split()))

x = [0 for x in range(100)]

for i in range(len(num_list)):
    a = list(combinations(num_list, i))
    number = len(a)
    for j in range(number):
        temp = sum(a[j])
        x[temp]=1

for k in range(len(x)):
    if x[1+k]==0:
        print(k+1)
        break

문제는 마땅히 다른 생각도 나지 않아서 일단 생각한대로 만들었다. 대충 정답은 찍히지만 for문만 4번이 들어간거를 보니 망한 코드인거 같다.

일단 파이썬 내장 함수인 combinations를 이용해서 모든 숫자의 조합을 계산하고 0으로 초기화한 리스트를 만든다음 해당 값이 있다면 1로 변경을 해준다.

그리고 가장 먼저 나오는 0을 찾아서 반환…….

답을 보자

동전에 대한 정보가 주어졌을때 화폐 단위로 오름차순 정렬한다. 이후 1부터 차례대로 특정한 금액을 만들 수 있는지 확인해보자1부터 target-1까지의 모든 금액을 만들 수 있다고 가정해보자. 작은 동전 순서대로 확인하며 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target금액을 만들 수 있다면 target값을 업데이트(증가)하는 방식을 이용한다.

예시 화폐 단위가 1,2,3,8을 가지고 있다.

1. 처음 금액 1을 만들 수 있는지 확인한다. target=1을 선언
2. target=1을 만족할 수 있는지 확인한다. 이미 화폐 1을 가지고 있어서 만들 수 있다. 이어서 target = 1+1 2로 업데이트 한다. (1까지의 모든 금액을 만들 수 있음)
3. traget=2를 만족할 수 있는지 확인한다. 현재 2라는 화폐를 가지고 있다. 따라서 target = 2+2 = 4가 된다.(3까지의 금액을 만들 수 있다)
4. traget=4를 만족할 수 있는지 확인한다. 3이라는 단위가 있다. 따라서 traget = 4+3 = 7 (6까지의 모든 금액을 만들 수 있다.
5. target=7를 만족하는지 확인한다. 이보다 큰 화폐 8인 동전이 있다. 따라서 금액 7을 만드는 방법은 없다. 정답은 7이다.

거스름돈 문제의 경우 거스름돈이 무한하지만 여기서는 제한되어 있다는 점이 다르다.

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

target = 1
for x in data:
    #만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    #print(target)
    target += x

#만들 수 없는 금액 출력
print(target)

아이디어를 사용하니 훨씬 간단해졌다.

1, 2, 3, 8을 가정할때

target는 1이고 여기서 1을 더해서 2까지 만들 수 있음을 거기서 2를 더해서 3까지 만들 수 있음을 3+4해서 7이되고 그러면 6까지 만들 수가 있고 문제는 7을 만들기 위해서는 남아 있는 동전이 7보다 작아야하지만 그보다큰 8이 들어와서

target < x 조건을 만족하여 빠져나온다.

알듯하면서 모르겠다. 나중에 다시 한번 보자