[C++] 백준 2293: 동전 1

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

 

조건을 보면 시간 제한과 메모리 제한이 빠듯한 문제이다.

그 점을 유의하지 않으면 몇 번이나 틀릴 수 있다 ㅠㅠㅠ

 

 

 

<풀이>

문제를 보면 n가지 종류의 동전으로 가치의 합이 k가 되도록 하는 경우의 수를 구하는 문제이다.

 

배열의 한 축을 가치의 합으로 두면 문제가 풀릴 거 같아 그대로 진행해봤다!

처음에는 동전의 종류도 배열의 한 축으로 둬서 2차원으로 생각해봤는데 풀이가 영 생각이 나지 않아서,

1차원으로 바꾸어서 진행했다.

 

 

먼저 예제를 통해 시뮬레이션을 돌려보자.

1원이 되는 경우: 1

2원이 되는 경우: 1 1  / 2

3원이 되는 경우: 1 1 1 / 1 2

4원이 되는 경우: 1 1 1 1 / 1 1 2 / 2 2

5원이 되는 경우: 1 1 1 1 1 / 1 1 1 2 / 1 2 2 / 5

6원이 되는 경우: 1 1 1 1 1 1 / 1 1 1 1 2 / 1 1 2 2 / 2 2 2 / 1 5

...

 

여기서 6원까지 시뮬레이션을 돌렸을 때 뭔가 감이 잡혔다.

6원의 경우가 총 5가지의 경우의 수가 있는데

1원짜리만 쓸 경우: 1 1 1 1 1 1

2원짜리까지 쓸 경우: 1 1 1 1 2 / 1 1 2 2 / 2 2 2

5원짜리까지 쓸 경우: 1 5

이렇게이다.

 

2원짜리까지 쓸 경우에서

1 1 1 1

1 1

0

에서 2원짜리를 쓸 때의 경우의 수가 더해지는 느낌이다!

 

5원짜리까지 쓸 경우도 보면

1

에서 5원을 더한다!!

 

즉, 코인의 종류마다 반복문을 돌린다고 가정했을 때,

가치의 합에서 각 코인의 가치만큼 뺀 값의 경우의 수를 더하면 될 것 같다!

 

 

점화식으로 표현해보면,

i를 코인의 종류, j를 가치의 합을 나타내는 변수라 했을 때,

dp[j] = dp[j - coin[i]] + dp[j];

위와 같은 점화식이 나온다.

 

단 주의할 점이 3가지 있다.

첫 번째, 6원의 경우의 수에서 보면 2 2 2 의 경우의 수가 있는데 이는 1원짜리 동전은 0개를 쓴 경우이다.

즉, 0원의 가짓수도 고려해주어야 한다는 뜻이다!!!

 

두 번째, dp[j - coin[i]]에서 coin[i]의 값이 크다면 j - coin[i]의 값이 음수가 되어버릴 수 있다.

이럴 경우 OutOfBounds 오류가 발생하므로 그 점도 유의해서 코드를 작성하자.

 

세 번째, 메모리 크기 제한이 4MB로 int형으로 치면 10^6정도까지이다.

dp 배열의 크기를 너무 크게 잡으면 메모리 초과가 될 수 있다.

 

 

전체 코드는 다음과 같다.

필자는 처음에 동전도 오름차순으로 정렬해야 하는 줄 알고 벡터로 coin[i]를 만들었는데, 하다보니 정렬은 필요없어 보였다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int dp[100005];
vector<int> coin;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin>>n>>k;
    for(int i = 0; i < n; i++){
        int tmp;
        cin>>tmp;
        coin.push_back(tmp);
    }

    dp[0] = 1;
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= k; j++){
            if(j >= coin[i]) dp[j] = dp[j-coin[i]] + dp[j];
        }
    }
    
    cout<<dp[k];
    return 0;
}