백준 2294 동전2

문제 링크

https://www.acmicpc.net/problem/2294

풀이 전 계획과 생각

이 문제는 동적 프로그래밍 문제에 해당한다. 즉 작은 문제의 결과를 기반으로 그 문제에 연결된 더 큰 문제를 푸는 방식으로 전체 문제를 해결한다.

소위 거스름돈 문제라고 불리는 문제로, 동전의 가치만 정해져 있고 개수는 무한정이며 특정 값을 나타내는 가장 적은 동전 개수를 찾는 것이 문제의 목표이다.

여기에서 기초가 되는 소문제는

• 0원은 동전 0개가 당연히 최소임 (마이너스 돈은 없으니 다른 방법으로 표현할 수도 없음)
• n₁원짜리 동전이 있다면 n₁원을 나타내는 방법의 최솟값은 당연히 n₁원짜리 동전 한 개임

여러가지로 스스로 코딩을 해보려고 했지만 계속 예외가 발생하여 결국은 거스름돈 문제에 대한 기초적인 이론을 조금 알아보았는데... 결국은 각각의 목표값에 대하여 존재하는 동전(물론 목표값보다 작은 액면가의 동전만)을 모두 넣어봐야 하는 것이었다.

즉, n-1원까지의 동전 수는 모두 계산했다고 가정했을 때 n원에서의 동전 개수는
n보다 작거나 같은 동전 c₁,c₂,c₃,c₄...가 있는 경우
n-cx에서 최솟값이 계산 가능한 경우들의 최솟값에 1을 더하면 된다.

예를 들어서 동전이 1원짜리와 2원짜리가 있다면
0원에서는 당연히 0개
1원에서는 1원짜리 동전에 대해서만 비교하는데 1-1=0원에서 0개라는 결과가 나와 있으니까 이에 1원짜리 동전 1개를 더한 1이 최솟값이고
2원에서는 1원짜리, 2원짜리 동전에 대해서 비교하는데
2-1=1에서는 1원의 최솟값 1이 있고
2-2=0에서는 0원의 최솟값 0이 있는데
이 중 최솟값인 0에 2원짜리 동전 1개를 더해서 1개가 2원의 최솟값이 된다.

풀이 (코드 블록 첨부)

#백준 2294 동전2
import sys
N,K=map(int,sys.stdin.readline().split())
counts = [-1 for x in range(K+1)]
counts[0]=0
coins=[0]
for x in range(N):
    coin=int(sys.stdin.readline())
    if coin<=K:
        coins.append(coin)
        counts[coin]=1
#print(counts)
coins.sort()
for i in range(1,len(counts)):

    smaller_coins=[]
    for c in coins:
        if c>i:
            break
        else:
            smaller_coins.append(c)
    previous_values=[]
    for c in smaller_coins:
        if counts[i-c]!=-1:
            previous_values.append(counts[i-c]) 
    if previous_values!=[]:
        counts[i]=min(previous_values)+1
'''

반례
2 10
2
3
3+3+2+2


'''
    
print(counts[-1])    

풀이하면서 막혔던 점과 고민

혹시나 모든 동전을 다 한번씩 빼 보는 것 말고 더 간단한 구조가 있을까 헛된 기대를 하고 한동안 오답의 늪에 빠져 있었다. ㅋㅋㅋ

풀이 후 알게된 개념과 소감

거스름돈 문제에 대해서 공부해보는 계기가 되었다.