동전 1 [백준 2293] - python

import sys
input = sys.stdin.readline

def BOJ2293() :
  n, k = map(int, input().split())
  l = []
  for _ in range(n) :
    l.append(int(input()))

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

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

 

접근방법 :

 

1. dp 배열은 가치별 경우의 수를 나타낸다

 

ex) dp[10]은 주어진 동전들을 이용하여 10을 만들 수 있는 경우의 수

 

1, 2, 5을 예로 들면 

 

6의 가치를 만드는 방법은

 

5를 구성했던 경우의 수에서 1을 하나씩 더해주는 방법과

4를 구성했던 경우의 수에서 2를 하나씩 더해주는 방법과

1을 구성했던 경우의 수에서 5를 하나씩 더해주는 방법입니다.

 

결국 6을 구성하는 방법은 1을 구성했던 방법 + 4를 구성했던 방법 + 5를 구성했던 방법들의 합입니다.

 

2. 1번의 내용을 점화식으로 나타내면 위의 코드의 내용과 같이 나타낼 수 있습니다.

 

 

 

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

2293번: 동전 1