[BAEKJOON] 2293 동전 1 - Python

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

2293번: 동전 1

 

 

 

<문제 풀이>

- 앞서 포스팅한 동전 문제와 같은 dp문제이다.

https://kcw0360.tistory.com/4

[BAEKJOON] 9084 동전 - Python

- 전체적인 풀이방법은 동일하다.

- 주어지는 금액을 가지고 해당금액을 만들 수 있는 경우의 수를 구하는 문제이다.

- 주어지는 금액을 순서대로 반복하고, 주어지는 금액에 해당하는 금액부터 반복문을 시작하며 경우의 수를 구한다.

 

 

 

<Code>

N, K = map(int, input().split())

coins = []    # 사용할 동전 종류
dp = [1] + [0] * K    # 경우의 수 체크

for _ in range(N):
    coins.append(int(input()))

for coin in coins:    # 해당 동전을 가지고 만들 수 있는 경우의 수 찾기
    for i in range(coin, K+1):    # i값을 만드는 데 있어서 coin 가치로 만들 수 있는 경우의 수는 i, i-coin가 같은 경우의 수를 가진다.
        dp[i] += dp[i-coin]

print(dp[K])

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.