백준2293🐨동전 1

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

 

아래 동영상의 도움으로 문제를 풀었습니다!

 

https://www.youtube.com/watch?v=LBOQikSpfNg

1, 2, 5 로 10 만들기

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5	5	6
5	1	1	2	2	3	4	5	6	7	8	10

$dp[i][j]$ $i$번째 동전 추가시 j원을 만드는 경우의 수

$$ $dp[i][j] = dp[i-1][j] +  dp[i][j-coin]$$

dp[0] =1

0원을 만드는 경우의 수는 1 (아무것도 안 쓴다.)

for coin in lst:

    for j in range(coin,k+1):

        dp[j] += dp[j-coin]

def calculate_budget(coin_type_count, target_money, coin_values):
    # dp 배열 초기화: dp[i]는 i 금액을 만들 수 있는 방법의 수를 저장
    dp = [0] * (target_money + 1)
    dp[0] = 1  # 0원을 만드는 방법은 아무것도 선택하지 않는 1가지 방법뿐임

    # 각 동전에 대해 반복
    for coin in coin_values:
        # 현재 동전의 가치부터 목표 금액까지 반복
        for amount in range(coin, target_money + 1):
            dp[amount] += dp[amount - coin]  # 현재 금액을 만들 수 있는 새로운 방법 추가

    return str(dp[target_money])

n, k, *coins = map(int, open(0).read().split())
open(1,'w').write(calculate_budget(n, k, coins))