[백준] 2293번 동전 1 - 파이썬(Python)

시간 제한

0.5 초 (추가 시간 없음)

문제 (링크)

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

2293번: 동전 1

 

나의 풀이

n, k = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))

dp = [0] * (k+1)
dp[0] = 1
# dp[i] -> i원을 만들 때 가능한 경우의 수
# dp[0] -> 동전 하나를 사용하는 경우 (coin이 3일 때, dp[3 - 3] = 1로 맞춰줌으로써 0원에서 3원을 더해 3원을 만드는 경우라고 생각)

for coin in coins:
    for i in range(coin, k+1):
        # coin원 동전으로 i원 만들기 -> i - coin원을 만든 후 coin원을 추가하는 것과 같음
        # 즉, coin원으로 동전을 만드는 경우의 수 -> dp[i - coin]원
        possible_cases = dp[i - coin]
        dp[i] += possible_cases

print(dp[k])

코드 설명 및 풀이법

시간제한이 0.5초로 DP를 이용해 아주 빠르게 풀어야하는 문제이다.

 

테스트 케이스를 예제로 점화식을 세워보자.

 

우선, 1원을 가지고 1 ~ 10원까지 만드는 경우의 수는 모두 1이다. 

 

그 다음으로, 1원과 2원을 가지고 1 ~ 10원까지를 만드는 경우의 수를 생각해보자.

 

2원으론 1원을 만들 수 없으니, 1원은 오직 1원으로만 만들 수 있으므로 경우의 수는 그대로 1이다.

 

2원을 만들기 위해선 기존에 1원으로만 만들었던 (1원, 1원)에 더해 새로 추가된 동전을 사용하는 경우(2원)가 추가되므로 2개가 된다.

 

3원을 만드는 경우를 보자.

 

우선, dp테이블에 3원을 1원으로 만드는 경우의 수는 이미 업데이트 되어있다.

 

2원이 추가됨으로써 만들어질 수 있는 경우의 수만 더해주면 되는 것이다.

 

이해하기 쉽게 직접 써보면, (1원, 1원, 1원)에 (1원, 2원)으로, 총 2가지 경우의 수가 존재하고, 2원이 추가되며 새로 만들어진 경우의 수는 (1원, 2원) 조합이다.

 

자, 여기서 3은 1과 2를 더한 수임을 주목하자.

 

그렇다면 3원을 만들 수 있는 경우의 수는 1원을 만들수 있는 경우에 2원을 그저 추가해준 것으로, 경우의 수 자체는 동일하다.

 

즉, dp[3] = dp[1]인 것이다. 

 

와닿지 않는다면 4원을 만드는 경우도 고려해보자.

 

4원은 (1원, 1원, 1원, 1원), (1원, 1원, 2원), (2원, 2원) 이렇게 총 3개의 조합으로 만들 수 있다.

 

4는 2와 2를 더한 수이다.

 

즉, 4원을 만들 수 있는 경우의 수는 2원을 만들 수 있는 경우에 2원 하나를 추가해준 것으로, 이 역시 경우의 수가 동일하다.

 

즉, dp[4] = dp[2]이다.

 

즉, dp[2]인 경우의 수 (1원, 1원)과 (2원) 조합에 각각 2원을 추가해주어 (1원, 1원, 2원), (2원, 2원)이 되고, 처음에 1원으로만 4원을 만들었던 경우의 수 한 가지 (1원, 1원, 1원, 1원)을 더하면 총 3가지의 경우의 수가 나온다.

 

이를 점화식으로 표현하면, dp[i] += dp[i - coin]이 된다.

 

 

DP문제를 잘 해결하기 위해선 2가지가 중요한 것 같다.

 

첫 번째는 점화식을 세우는 것이고, 두 번째는 dp[i]에 도달하기 이전인 0 ~ i - 1 까지는 최적의 값이 저장되었다고 확신하는 것이다.

 

구현 문제처럼 즉각적으로 답이 보이는 게 아니기 때문에, 자꾸 예외처리에 신경을 쓰게 되고 그러다보면 정확한 점화식을 세우는 데 집중하지 못하게 된다.

 

DP는 점화식으로 푸는 문제임을 명심하자.