[BOJ, Python] 2294번_동전 2

백준 2294번_동전

큰 어려움 없이 푼 문제이다. 개인적으로 이 문제보다 DP 실버1 문제들이 더 어려웠던거 같다.

n가지 동류의 동전, 가치의 합이 k원이 되도록, 동전의 개수가 최소 이 3가지를 보면 해당 문제를 DP로 풀어야하는 것은 금방 알 수 있다.

동전 종류의 갯수 n과 타겟이 되는 k의 범위를 보면 1<=n<=100, 1<=k<=10000 이므로 머리에 떠오르는대로 단순하게 풀어도 시간 초과를 발생하지 않을거라고 생각해서 아래와 같은 과정으로 문제를 접근했다.

1. i원을 만들기 위해 필요한 동전의 갯수를 저장할 리스트를 만든다. (name: dp)
2. 리스트 원소의 초기값은 int(1e9)로 매우 큰 값을 주고, 리스트 원소의 수는 n의 최댓값이 100,000이기 때문에 100,001개로 한다.
3. 탑-다운 방식으로 dp 리스트를 돌면서 i번째 dp의 값이 0이 아닌 경우 i+모든 동전의 가치(n가지 종류의 동전의 정보들)를 더해 min으로 비교해 dp(i+(동전의 가치))에 저장한다.

이 문제는 글로 보는 것보단 코드를 보는 것이 이해가 쉬울 것 같다.

풀이 코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
dp = [int(1e9)]*(100001) # i원을 만들 때 사용되는 동전의 갯수
coin = [] # n개 동전의 가치를 저장할 리스트
for _ in range(n):
    c = int(input())
    coin.append(c)
    dp[c] = 1

s = min(coin) # 시작점

for i in range(s, k+1):
    if dp[i] == 0: # dp[i]가 0이라면 i원은 동전의 조합으로 만들지 못하는 액수이기에 건너뛰기
        continue

    for c in coin: # 모든 동전을 돌며 동전 갯수의 최솟값 찾기
        if (i+c)<=k:
            dp[i+c] = min(dp[i]+1, dp[i+c])

if dp[k] == int(1e9): # k원을 만들지 못하는 경우 -1 출력
    print(-1)
else:
    print(dp[k])

결과