Baekjoon 2293. 동전 1 / Python

2293. 동전 1

난이도 : 골드 4
소요 시간 : 10분
날짜 : 2025.01.09
언어 : 파이썬
알고리즘 유형 : dp

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 동전의 종류가 주어진다.
2. 적당히 조합해서(중복가능, 순서없음) k원을 만드는 가지수를 구한다.

2. 해결 방식

1. dp[i] = i원을 만드는 경우의 수
2. 점화식
   • 동전 c에 대해서 dp[i] += dp[i-c]이다.
   • 이 때, i는 c~k 사이여야 한다.

3. 정답 코드

import sys;input = sys.stdin.readline

n, k = map(int, input().split())
dp = [1] + [0] * k  # dp[i] : i원을 만드는 경우의 수

for coin in [int(input()) for _ in range(n)]:
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

print(dp[k])