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

 

2293번: 동전 1

문제

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

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

입력

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

출력

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

 

예제 입력  3 10 1 2 5

예제 출력  10

 

풀이

 

주어진 동전들로 k 원을 만드는 가짓수를 찾는 문제이다.

메모리 제한이 4mb로, 공간복잡도까지 요구하는 문제이다. (파이썬에서는 이보다 더 많긴 하다.)

 

DP(다이나믹 프로그래밍)를 적용하기 위해서는 우선 부분 문제로 나눌 수 있는지부터 고려해야 한다.

여기서, 동전의 가짓수를 제한하는 방법을 생각할 수 있다.

 

또한 DP 에 빠질 수 없는 요소인 메모이제이션을 적용할 수 있는가도 생각해야 한다.

여기서는 0원부터 k원까지 만들 수 있는 경우의 수를 생각할 수 있다.

 

이제 예제를 활용하여 1부터 2원, 5원을 차례로 적용해나가며 경우의 수를 탐색해보자.

 

우선 1원만을 적용할 때의 가짓수는 당연히 각 n원 별로 1가지 뿐이다.

동전 한 가지 종류로는 쭉 나열하는 방식으로밖에 구성하지 못하기 때문이다.

따라서 메모이제이션 배열인 dp는 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 꼴로 구성된다.

 

이제 여기에 나머지 동전으로 만들 수 있는 가짓수를 탐색한다.

처음에는 단순히 n원을 동전으로 나눈 몫을 경우의 수로 추가하면 될 것이라고 생각했다.

즉, 10 원을 만들기 위해서는 처음 가짓수인 1 + 10//2 + 10//5 꼴로 말이다. 하지만 이 경우 8로, 예제의 답인 10과 다르다.

 

왜냐하면 사실, 5원을 무조건 사용하여 만들 수 있는 경우의 수는

 

55

5221

52111

511111

 

이렇게 4가지이기 때문이다. 10//5 인 두 가짓수가 아니다.

여기에서 메모이제이션을 생각해볼 수 있다.

 

사실 우리는 이미 답을 구해놓은 셈이다.

10원을 만들 때 5원을 추가할 경우 추가되는 가짓수는 dp[5]에 있다.

 

코드가 순차적으로 진행되어 현재 탐색 동전이 5원이고 dp[10]을 구할 때 dp[5]는

11111

221

2111

5

 

이렇게 4가지로 구성되게 된다.

 

즉, 현재 탐색하는 동전을 i, 현재 구하는 x원을 j라고 할 때, dp[i] - dp[j-i]가 성립된다는 것이다.

동전별 dp 배열을 보면 다음과 같다.

 

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

[1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10]

 

동전의 자릿수를 맞추기 쉽게 k+1 로 구성한다.

또한, 인덱스 0은 현재 동전만 사용했을 경우를 의미하기도 한다.

 

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
cl = sorted([int(input()) for i in range(n)])
dp = [1 if i%cl[0] == 0 else 0 for i in range(k+1)]
# 맨 처음 동전으로 나누어 떨어지는 x원들만 1로 생성한다.
# 만약, 맨 처음 동전이 1이 아닌 2이상일 경우를 생각해보자.
cl.remove(cl[0])

for i in cl:
    for j in range(i,k+1):
        dp[j] += dp[j-i]
print(dp[k])