[알고리즘] 만들 수 없는 금액

*K대회 기출

문제 설명

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

 

예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.

 

생각의 흐름

I) 하...더해서 못 만드는 값들 사이의 규칙이 있지 않을까? 좀 생각해보자.

 

II) 아니 예제 즉 동전의 값은 얼마든지 바뀔 수 있는데 규칙을 찾는게 의미가 있을까? 걍 0부터 시작해서 계속 1을 더해가면 언젠가는 못만드는 시점이 나올 것이고 그때의 값을 출력하면 될 것 같은데? 

 

III) 다 좋은데 그 수가 동전을 더해서 못만든다는 사실을 어떻게하면 확인할 수 있을까?

 

IX) 일단 상식적으로 동전이랑 같은 수는 만들 수 있다. 아 그렇찮아. 이건 너무 당연한 사실이다. 그래서 일단 같은 값을 일단 지우자. 

 

X) 그 다음에 나머지 경우들을 보면 동전의 값이 담긴 리스트를 역순으로 한 다음에 값들에서 뺴주고 0이 되지 않는 경우가 더해서 못만드는 경우일 것이다. 물론 0보다 더 작아질 수 있기 떄문에 그 부분은 예외처리로 빼주면 되겠다.

 

 

코드

n = int(input())
lst = list(map(int, input().split()))
lst.sort()
result = list(range(1, max(lst))) # 1원 ~ 가장 큰 금액-1 에서 답이 나옴.

# 1) 같은 값 지우기 (result에 있는 것 중 lst와 중복되는 것 제거)
for i in range(1, max(lst)):
    if i in lst:
        result.remove(i)

# 2) 합쳐서 나오는(lst 원소의 조합) 값 지우기 (5 = 2+ 3)
for j in result: # 4, 5, 6, 7, 8 중 4부터
    tempt = j
    for x in lst[::-1]: # 9 3 2 1 1 역순
        if tempt - x >= 0:
            tempt -= x
    if tempt != 0:
        print(j)
        break

 

두번째 시나리오가 이 코드의 핵심인데 이제 동전을 역순으로 설정한 다음에 temp - 동전을 시전한다. 이때 그 값이 0보다 크거나 같다가 확인된 경우만 연산을 수행한다. 그렇게 모든 동전을 걷쳐간 temp가 0이 되지 않았다면 동전으로 만들 수 없는 수인 셈이다.