백준2293_동전 1

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

n개의 동전으로 k가격을 만들 수 있는 경우의 수를 구하는 DP 문제이다.

• dp테이블을 만들면 위와같다.
• 1원 동전을 가지고 1~k 까지의 각각의 가격을 만들 수 있는 경우의 수를 표시하면 전부 1이다.
• 2원 동전을 추가한다면, dp[k](현재 k원을 만들 수 있는 경우의 수) + dp[k-2](2원을 더했을 때 k원이 되는경우의 수) 두 가지를 더하면 해당 k원을 만들 수 있는 경우의 수가 나온다

n, k = map(int,input().split())
coins = [int(input()) for _ in range(n)]
dp = [0] * (k + 1)
dp[0] = 1


for coin in coins:
    for price in range(coin, k + 1):
        dp[price] += dp[price-coin]
print(dp[k])

💯 생각보다 간단하게 코드가 구현 되는데 풀지는 못했다,,,,