BOJ 2293 - 동전 1 문제풀이

문제를 읽고 이해하기

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

 

각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

입력

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

 

출력

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

 

재정의와 추상화

이 문제는 포인트를 잘 잡으면 정말 쉽게 풀 수 있지만, 포인트를 못잡고 헤매는 경우 굉장히 번거롭게 느껴질 수 있는 문제이다. 필자도 문제를 풀다 못해 결국 구글링을 통해 방법을 얻었다.. 참고문서

 

동전의 종류는 n가지가 있으며, 무한정 사용할 수 있다. 이 동전들을 적당히 사용하여 합이 k원이 되도록 하여야 한다. DP를 푸는 방법론 중 하나로 테스트 케이스를 이용해 처음부터 순서대로 절차를 따라가보는 것이다.

 

문제에서 주어진 n = 3, k = 10의 케이스를 생각해보자.

 

1원을 만드는 방법은 1원으로만 1원을 만드는 경우이다.

2원을 만드는 방법은 1원과 2원으로만 2원을 만드는 경우이다.

4원을 만드는 방법은 1원과 2원으로만 4원을 만드는 경우이다.

5원을 만드는 방법은 1원과 2원으로만 5원을 만드는 경우와 5원 1개로 5원을 만드는 경우이다.

 

여기서 규칙성을 찾을 수 있다.

 

M원을 만드는 방법은, M원보다 작거나 같은 가치를 가지는 동전을 이용해 M원을 만드는 방법이다.

 

예시를 통해 더 자세히 알아보자.

 

5원을 만드는 방법

= 1원과 2원을 통해 5원을 만드는 방법 + 5원을 통해 5원을 만드는 방법

= 1원과 2원을 통해 5원을 만드는 방법 + (5 - 5)원을 통해 5원을 만드는 방법 (5원 1개를 쓴 경우)

 

6원을 만드는 방법

= 1원, 2원, 5원을 통해 5원을 만드는 방법

= 1원과 2원을 통해 5원을 만드는 방법 + 5원 1개를 통해 6원을 만드는 방법

= 1원과 2원을 통해 5원을 만드는 방법 + 1원과 2원을 통해 (10 - 5)원을 만드는 방법 (5원 1개를 쓴 경우)

 

10원을 만드는 방법

= 1원, 2원, 5원을 통해 10원을 만드는 방법

= 1원과 2원을 통해 10원을 만드는 방법 + 5원 1개를 통해 10원을 만드는 방법 + 5원 2개를 통해 10원을 만드는 방법

= 1원과 2원을 통해 10원을 만드는 방법 + 1원과 2원을 통해 (10 - 5)원을 만드는 방법 + 1원과 2원을 통해 (10 - 10)원을 만드는 방법

 

테이블을 통해 자세히 알아보자.

i	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
0	1	0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5	5	6
3	1	1	2	2	3	4	5	6	7	8	10

 

즉, 이러한 규칙성을 통해 코드를 작성하면 아래와 같다.

dp[0][0] = 1;
for (int i = 1; i <=k; i++)
    dp[0][i] = 0;

for (int i = 1; i <= n; i++) {
    dp[i][0] = 1;
    for (int j = 1; j <= k; j++) {
        dp[i][j] = dp[i - 1][j];
        for (int l = 1; l <= j / coins[i]; l++)
            dp[i][j] += dp[i - 1][j - coins[i] * l];
    }
}

i는 처음부터 i번째 까지의 종류를 사용한다는 의미.

예를 들어 i = 2이면, 1원, 2원, 5원 중 1원, 2원만 사용한다는 것.

 

위 코드는 i개의 동전 종류를 이용하여 j원을 만드는 방법이다.

 

위 테스트 케이스를 예로 들어 절차를 설명하면, 먼저 1개 동전 종류를 이용하여 1원부터 k원을 만드는 방법을 만들고, 그 다음 2개의 동전 종류를 이용하여 1원부터 k원을 만드는 방법을 만들고, 그 다음 3개의 동전 종류를 이용하여 1원부터 k원을 만드는 방법을 만든다.

 

 

위에서 설명한 것 처럼

 

i개의 종류를 이용해 j원을 만드는 방법

= i번째 동전을 제외한 i - 1개의 종류를 이용해 j원을 만드는 방법 + i번째 동전을 1개 이상 이용해 j원을 만드는 방법

 

을 사용하여 최종적으로 n개의 종류(모든 종류)를 이용해 k원을 만드는 방법을 구하게 되고, 이 값이 답이 된다.

 

 

그러나 위와 같이 코드를 작성하면 문제에서 주어진 (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)이라는 최대 경우를 생각하여 배열을 선언하면, dp의 값을 저장할 int dp[101][10001], 동전의 가치를 저장할 int coins[101]을 선언하게 된다.

 

그런데 이 경우, 메모리를 생각해보면 4 byte * (101 * 10001 + 101) + 기타 사용 메모리를 생각해보면 문제에서 주어진 최대 메모리 값인 4MB를 넘어버릴 것이다. (대개 메모리가 128MB, 256MB 이렇게 주어지지만, 4MB처럼 엄청 작게 주어지는 경우에는 꼭 메모리를 생각해봐야 한다.)

 

 

따라서, 메모리를 줄여야 하는데, 동전의 가치는 무조건 저장해야하니 coins의 배열 사이즈는 조절할 수가 없다. 그러면 우리가 dp를 수행할 반복문을 유심히 보면, 다음 dp값은 오롯이 해당 i의 이전 값인 i - 1 번째의 dp값과 i 번째의 coins값에만 의존한다. coins는 건들이지 않으니 무시하면, i - 1 번째의 dp값에 의존한다는 의미이다.

 

이를 생각해보면 우리가 궁극적으로 얻고자 하는 것은, 마지막 번째의 dp값이다. k번째의 dp값인 것이다. 즉, 우리는 그 전 (i - 1) 번째의 dp값만 필요하고 그 보다 더 이전의 dp 값은 쓸 일이 없다.

 

그래서 우리는 dp를 1차원 배열로 dp[10001]로 선언하고, 현재 dp값을 int temp[10001]에다가 복사해놓고, dp[i]는 temp[i - 1]을 통해 갱신하면 된다!

 

이렇게 하면 원래의 메모리에 2/101(대략 0.01%) 만큼만 사용하면 된다!

 

코드 작성

#include <iostream>

using namespace std;

int main() {
    int dp[10001];
    int coins[101];
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> coins[i];

    dp[0] = 1;
    for (int i = 1; i <= k; i++)
        dp[i] = 0;

    for (int i = 1; i <= n; i++) {
        int temp[10001];
        copy(dp, dp + k + 1, temp);
        for (int j = 1; j <= k; j++) {
            dp[j] = temp[j];
            for (int l = 1; l <= j / coins[i]; l++)
                dp[j] += temp[j - coins[i] * l];
        }
    }
    cout << dp[k];

    return 0;
}