백준 2293 동전1 C++ 풀이

문제

문제 링크

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

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

입력

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

출력

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

첫 번째 풀이(실패)

로직

예제

3 10
1
2
5

예제를 기준으로 로직이 어떻게 흘러갈지 생각해보았다.

5 5
5 2 2 1
5 2 1 1 1
5 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

높은 가치의 코인부터 차례대로 사용했다가 기준값(k)이상이 되면 더 작은 코인으로 대체해 경우의 수를 만드는 방법이 가장 먼저 떠올랐다.
위 로직을 코드로 구현했다.

코드

int n, sum, ans;
int coin[101]; 

void go(int curCoinIdx, int curSum) {
    curSum += coin[curCoinIdx];

    if (curSum == sum) {
        ans++;
    }
    if (curSum >= sum) { // 코인합이 기준치를 넘기면 종료
        curSum -= coin[curCoinIdx];
        return;
    }
    int nextCoinIdx = curCoinIdx;
    while (nextCoinIdx >= 0) { // 높은 가치의 코인부터 낮은 가치의 코인까지 차례대로 선택
        go(nextCoinIdx, curSum);
        nextCoinIdx--;
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> sum;
    for (int i = 0; i < n; i++) {
        cin >> coin[i];
    }
    for (int i = n - 1; i >= 0; i--) { // 높은 가치의 코인부터 선택
        go(i, 0);
    }
    cout << ans;
}

결과는? 시간초과!
위 방법을 사용하면, 기준값 이상이 될 때까지 모든 경우의 수를 하나하나 구하게 된다.

예제를 기준으로 각 함수에서 선택한 코인들을 출력하게 하면 다음과 같다.

현재 선택한 코인들 : 5 , 합계 : 5
현재 선택한 코인들 : 5 5 , 합계 : 10
현재 선택한 코인들 : 5 2 , 합계 : 7
현재 선택한 코인들 : 5 2 2 , 합계 : 9
현재 선택한 코인들 : 5 2 2 2 , 합계 : 11
현재 선택한 코인들 : 5 2 2 1 , 합계 : 10
현재 선택한 코인들 : 5 2 1 , 합계 : 8
현재 선택한 코인들 : 5 2 1 1 , 합계 : 9
현재 선택한 코인들 : 5 2 1 1 1 , 합계 : 10
현재 선택한 코인들 : 5 1 , 합계 : 6
현재 선택한 코인들 : 5 1 1 , 합계 : 7
현재 선택한 코인들 : 5 1 1 1 , 합계 : 8
현재 선택한 코인들 : 5 1 1 1 1 , 합계 : 9
현재 선택한 코인들 : 5 1 1 1 1 1 , 합계 : 10
현재 선택한 코인들 : 2 , 합계 : 2
현재 선택한 코인들 : 2 2 , 합계 : 4
현재 선택한 코인들 : 2 2 2 , 합계 : 6
현재 선택한 코인들 : 2 2 2 2 , 합계 : 8
현재 선택한 코인들 : 2 2 2 2 2 , 합계 : 10
현재 선택한 코인들 : 2 2 2 2 1 , 합계 : 9
현재 선택한 코인들 : 2 2 2 2 1 1 , 합계 : 10
현재 선택한 코인들 : 2 2 2 1 , 합계 : 7
현재 선택한 코인들 : 2 2 2 1 1 , 합계 : 8
현재 선택한 코인들 : 2 2 2 1 1 1 , 합계 : 9
현재 선택한 코인들 : 2 2 2 1 1 1 1 , 합계 : 10
현재 선택한 코인들 : 2 2 1 , 합계 : 5
현재 선택한 코인들 : 2 2 1 1 , 합계 : 6
현재 선택한 코인들 : 2 2 1 1 1 , 합계 : 7
현재 선택한 코인들 : 2 2 1 1 1 1 , 합계 : 8
현재 선택한 코인들 : 2 2 1 1 1 1 1 , 합계 : 9
현재 선택한 코인들 : 2 2 1 1 1 1 1 1 , 합계 : 10
현재 선택한 코인들 : 2 1 , 합계 : 3
현재 선택한 코인들 : 2 1 1 , 합계 : 4
현재 선택한 코인들 : 2 1 1 1 , 합계 : 5
현재 선택한 코인들 : 2 1 1 1 1 , 합계 : 6
현재 선택한 코인들 : 2 1 1 1 1 1 , 합계 : 7
현재 선택한 코인들 : 2 1 1 1 1 1 1 , 합계 : 8
현재 선택한 코인들 : 2 1 1 1 1 1 1 1 , 합계 : 9
현재 선택한 코인들 : 2 1 1 1 1 1 1 1 1 , 합계 : 10
현재 선택한 코인들 : 1 , 합계 : 1
현재 선택한 코인들 : 1 1 , 합계 : 2
현재 선택한 코인들 : 1 1 1 , 합계 : 3
현재 선택한 코인들 : 1 1 1 1 , 합계 : 4
현재 선택한 코인들 : 1 1 1 1 1 , 합계 : 5
현재 선택한 코인들 : 1 1 1 1 1 1 , 합계 : 6
현재 선택한 코인들 : 1 1 1 1 1 1 1 , 합계 : 7
현재 선택한 코인들 : 1 1 1 1 1 1 1 1 , 합계 : 8
현재 선택한 코인들 : 1 1 1 1 1 1 1 1 1 , 합계 : 9
현재 선택한 코인들 : 1 1 1 1 1 1 1 1 1 1 , 합계 : 10

문제에 따르면 경우의 수는 최대 2^31이다. 시간 제한은 0.5이다. 1초당 약 1억번의 연산이 가능하기에 0.5초로는 2^31번의 연산을 수행하기에 부족하다.

두 번째 방법(DP)

로직

때문에 DP를 활용해야겠다고 생각했다.
m원을 만들기 위한 방법이 몇 가지가 있는 지를 낮은 가치의 동전부터 차례대로 계산하면 모든 경우의 수를 탐색하지 않고도 합이 k인 경우의 수를 알 수 있다.

동전의 종류는 최대 100가지이므로 0.5초안에 구할 수 있다.

그럼 로직이 어떻게 흘러갈지 예시를 통해 봐보자.
현재 2원과 3원이 존재하며, 이 두 가지 종류의 동전을 사용해 10원어치를 만드는 방법을 계산해보자.

먼저 2원을 가지고 만들 수 있는 값은 다음과 같다.

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

2원보다 작은 1원어치는 당연히 만들 수 없으며, 2이상의 짝수값을 생성할 수 있다.

2원과 3원을 가지고 만들 수 있는 값은 다음과 같다.

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

3원을 가지고 m원을 만들고 싶다면, m-3원을 만들 수 있는 경우의 수 + 1 을 해주면 된다.
m - 3원에 3원을 더하면 m원 어치를 만들 수 있기 때문이다.

2원과 3원을 가지고 7원을 만들고 싶다고 해보자. 4원어치에서 3원을 더하면 7원을 만들 수 있다. 현재 2원 두 개로 4원어치를 만들 수 있는 경우의 수가 하나 존재한다.

때문에 2원과 3원을 가지고 7원을 만드는 경우의 수는 4원을 만들 수 있는 경우의 수 + 1 이 된다.

이처럼 작은 가치의 동전부터 차례대로 경우의 수를 계산하면 100번의 연산으로 k어치의 동전을 만들 수 있는 경우의 수를 구할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, sum, ans;
int coin[101];
int dp[10001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> sum;
    for (int i = 0; i < n; i++) {
        cin >> coin[i];
    }

    for (int i = 0; i < n; i++) {
        if (coin[i] > sum) {
            continue;
        }
        dp[coin[i]]++; // i원 코인 하나로 무조건 i원 어치를 만들 수 있으므로 1추가
        for (int j = coin[i]; j <= sum; j++) {
            dp[j] = dp[j] + dp[j - coin[i]];
        }
    }
    cout << dp[sum];
}

dp[coin[i]]에서 1을 더해주는 로직

if (coin[i] > sum) {
        continue;
}
dp[coin[i]]++;

k값보다 더 큰 동전이 들어올 수도 있기 때문에, 위와 같이 동전의 값이 k보다 크면 넘기고, 이하이면 dp[coin[i]]를 1 상승시켜주는 것을 볼 수 있다.
dp[coin[i]]를 무조건 1 상승 시켜주는 이유는 i원동전 하나로 무조건 i원 어치를 만들 수 있기 때문이다. (3원동전 하나로 무조건 3원을 만들 수 있다.)

dp[0]을 1로 해두면 위 로직보다 좀 더 깔끔하게 코드를 짤 수 있다. 현재 로직에서 dp[j] = dp[j] + dp[j - coin[i]]를 통해 경우의 수를 갱신하고 있다. 이때 i원동전으로 i원어치를 구하는 경우의 수는 dp[i] = dp[i] + dp[i - i] 즉, dp[i] + dp[0] 이 된다.
때문에 dp[0]을 1로 설정해두면 동전이 자기 자신 하나를 사용할 때 1만큼을 더할 수 있게 해준다.

#include <bits/stdc++.h>

using namespace std;

int n, sum, ans;
int coin[101];
int dp[10001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> sum;
    for (int i = 0; i < n; i++) {
        cin >> coin[i];
    }
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = coin[i]; j <= sum; j++) {
            dp[j] = dp[j] + dp[j - coin[i]];
        }
    }
    cout << dp[sum];
}