문제

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

나의 코드

"""
1. 아이디어

2. 시간복잡도
O(nk) 정도? 근데 nk보단 확실히 적게 걸릴듯 -> coin의 숫자가 계속 늘어나니깐 두번째 반복문도
그만큼 덜 반복하게 될 것임
"""

from sys import stdin
input = stdin.readline

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

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

for coin in coins:
    for i in range(coin, k+1):
    	# coin원으로 동전을 만드는 경우의 수 -> dp[i - coin]원
        dp[i] += dp[i-coin]

print(dp[k])

    

느낀점

처음 풀면 맞출 수 있을까 하는 문제..;;

• n = 2, k = 4인 경우를 살펴보자.

이때는 1, 2원의 동전을 가지고 4원을 만드는 경우의 수를 구해야 한다.
경우의 수를 구해보면 다음과 같다.

1 + 1 + 1 + 1
1 + 1 + 2
2 + 2

이때, 1 + 1 + 1 + 1은 이미 n = 1, k = 4일때 구해져 있으므로 나머지 경우를 살펴봐야 하는데 1 + 1 + 2와 2 + 2는 n = 2, k = 2인 시점에서 단순히 +2만 해준 경우와 같다.

• 다음으로 n = 2, k = 6인 경우를 살펴보자.

이때는 1, 2원의 동전을 가지고 6원을 만드는 경우의 수를 구해야 한다.
경우의 수를 구해보면 다음과 같다.

1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 2
1 + 1 + 2 + 2
2 + 2 + 2

이때, 1 + 1 + 1 + 1 + 1 + 1은 이미 n = 1, k = 6일때 구해져 있으므로 나머지 경우를 살펴봐야 하는데 1 + 1 + 1 + 1 + 2와 1 + 1 + 2 + 2와 2 + 2 + 2는 n = 2, k = 4인 시점에서 단순히 +2만 해준 경우와 같다.

위의 두가지 결과를 토대로 점화식을 작성하면 dp[i] = dp[i-coin] 이 나온다.