[Baekjoon] #2293 동전1

SunYerim·2023년 1월 25일
0
post-thumbnail

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력 및 출력

내가 생각한 logic 및 코드

'''logic
    "점화식"
    1. dp테이블
    2. n원을 만들 수 있는 경우의 수는 이전 행의 n원을 만들 수 있는 경우의 수와
       n원에서 현재 동전의 가치 k원을 뺀 가치의 경우의 수의 합으로 이루어짐.
    ==> dp[n] = dp[n] + dp[n-k] (if n-k >= 0)'''

n, k = map(int, input().split())
coin = list(int(input()) for i in range(n))

dp = [0 for _ in range(k+1)]
dp[0] = 1

for i in coin:
    for j in range(i, k+1):
        if (j-i) >= 0:
            dp[j] += dp[j-i]

print(dp[k])

dp문제는 점화식 세우기가 8할인듯 !

profile
내 안에 있는 힘을 믿어라.

0개의 댓글