[백준/2293/파이썬] 동전 1

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

2293번: 동전 1

Problem

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

조건

• 각각의 동전은 몇 개라도 사용할 수 있다.
• 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
• 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.
• 동전의 가치는 100,000보다 작거나 같은 자연수이다.

SOL

간단한 문제처럼 보이지만, 쉽지않은 문제였다.

동전의 경우의 수를 구하는 문제는 많이 볼 수 있지만, 이와 같이, 동전의 종류자체가 정해져있지 않고, 유동적인 경우는 처음보긴 한다. 그래도, 일단은 예시를 보면서, 1,2,5원으로 10원을 나타내는 경우의 수를 하나씩 구해봤다.

 

• 1원 : 1 
• 2원 : (1+1),2 
• 3원 : (1+1+1),(1+2) 
• 4원 : (1+1+1+1),(1+1+2),(2+2) 

한가지 규칙성은 보인다. 

4원의 경우의 수를 보면, 2원 + (2원을 나타내는 경우의수) , 1원으로만 나타내는 경우의 수 와 같이, 이전 값이 재활용 되는걸 볼 수 있다. 즉, 재귀적인 관계를 형성하고 있음.

 

DP table로 한번 작성해보자.

이때, 정의를 DP[N][K] = N원으로 , N원을 포함하면서 K원을 만들 수 있는 경우의 수

• DP[2][3] = 2원으로, 2원을 포함하면서, 3원을 만들 수 있는 경우의 수 => (1,2)
• DP[2][4] = 2원으로, 2원을 포함하면서, 4원을 만들 수 있는 경우의 수 => (2,2) (1,1,2,2)

이렇게, 테이블을 작성하면, 좀 더 왜 DP인지 와닿게된다.

4원을 2원을 포함하면서, 만들 수 있는 경우는, 2원을 1개는 무적권 써야하기 때문에, 2원을 나타내는 경우의 수와 같다.

마찬가지로, 8원을 2원을 포함하면서, 만들 수 있는 경우는, 2원 1개는 무적권 써야하기 때문에, 6원을 나타내는 경우의 수와 같다.

 

그렇다면, 우리가 구하는 답은, DP[1][10]+DP[2][10]+DP[5][10]이고, 이건 K열을 다 더하는것과 같다.

 

• 하지만, 메모리 제한이 4MB이기 때문에, 2차원 배열을 1차원 배열로 압축시키는 방법을 생각해야한다.
• 어차피, 누적합을 계속 갱신시키는 형태이기 때문에, 1차원 배열에 계속 누적합을 쌓아가는 형식으로 바꿔줘도 무방하다. 
•  

import sys
input = sys.stdin.readline
N,K = map(int,input().split())

# 리스트 압축을 하기위해서, coins를 따로 받음.
coins=[int(input().rstrip()) for _ in range(N)]

DP =[0]*(K+1)
# n원을 n원으로 나타내는 방법
# DP[j-i]의 첫 반복은 DP[0]이기 때문!
DP[0] = 1
for i in coins:
    for j in range(i,K+1):
        DP[j] += DP[j-i]
        #print(DP)

print(DP[K])