[백준/2293] 동전 1 (Python)

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

2293번: 동전 1

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:12:47

 

---

 

문제 설명

 

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

입력 및 출력

 

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

 

입력 예시

3 10
1
2
5

 

출력 예시

10

 

 

---

 

풀이

 

1차원 DP로도 해결 가능한 문제이며, 시간복잡도는 최악의 경우 약 O(NK)가 소모된다.

 

DP[j]를 현재까지(1 ~ i-1 동전을 사용하였을 때) 진행하였을 때 동전 가치의 합이 j인 경우의 수라고 가정하자. 현재 동전의 가치가 coin[i]라면, 단순히 DP[j + coin[i]]는 (DP[j] 의 경우의 수 x 동전 가치 coin[i]를 더해주는 경우의 수)가 되므로, 바로 더해줄 수 있다. DP[0] = 1로 초기화하고(하나도 동전을 내지 않는 경우의 수) 모든 i, j에 대해 재귀적으로 탐색을 시행하면 DP 리스트 전체를 구할 수 있다. 마지막으로 DP[K]를 출력하면 끝.

 

 

 

 

풀이 코드

import sys
input = sys.stdin.readline

def init() :
  global n, k, coin_list
  n, k = map(int, input().split())
  coin_list = [int(input()) for _ in range(n)]

  return coin_list

def make_dp(coin_list) :
  dp = [0]*(k+1)
  dp[0] = 1
  
  for i in range(n) :
    for j in range(k+1) :
      if dp[j] > 0 and j + coin_list[i] <= k :
        dp[j + coin_list[i]] += dp[j]

  return dp

def solve() :
  coin_list = init()
  dp = make_dp(coin_list)
  print(dp[-1])

solve()

풀이 완료~