[백준]2293번 동전1 - python 파이썬

문제

 

 

 

처음 이 문제를 접했을 때 어떤식으로 구현을 해야할 지 전혀 감이 잡히지 않아서 구글링의 도움을 받았다.

 

이 문제는 dp 알고리즘을 이용해서 구현해주면 되는데 점화식을 만들어 내는게 쉽지 않았다.

 

동전이 담긴 coins 리스트를 돌면서  i원을 만들기 위한 경우의 수를 dp[i] 따라 저장해주는 방식으로 문제를 해결해주면 된다

이를 식으로 세우면

 

 

dp[i] = dp[i] + dp[i-c]  이렇게 되는데 이는

 

DP [4] (1,2 원으로 4를 만드는 경우의 수) = DP[4] (원래 1원으로만 4를 만드는 경우의 수) + DP[4 - 2] (1, 2 원으로 2를 만드는 경우의 수, 여기서 2원만 추가해주면 4가 되기때문)

 

 

이렇게 이해해주면 된다

 

코드

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

#k원 짜리 동전으로 k원을 만드는 경우의 수 추가
dp[0] = 1


for c in coins:
    for j in range(c,k+1):
        dp[j] = dp[j] + dp[j-c]

print(dp[k])

 

 

dp 는 항상 식을 세우는 부분이 가장 어려운 것 같다....

 

많이 연습이 필요한 부분이다