[C++] 백준 2293 - 동전 1 [Gold5]

출처

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

풀이 전략

동전의 합을 만족하는 경우의 수를 구하는 문제이다. 다른 알고리즘으로도 풀 수 있겠지만, 중복을 허용하지 않는다는 점과 동전의 금액이 그때그때 입력 받는다는점이 DP로 해야하는 이유라고 생각해서 DP로 풀이를 하였다.

풀이

먼저, 1원만 있을 때 만족하는 경우의 수와 2원이 추가되었을 때의 경우의 수를 보면 2원이 추가되었을 때 특징이 보이는데, 2의 배수인 2, 4, 6, 8, 10에서 경우의 수가 1씩 증가한다는 점이다. 그러나 이것 만으로 점화식을 구하면 틀릴 가능성이 존재하기 때문에 5원을 추가했을 때의 경우의 수도 구해보았다.

5원을 추가했을 때를 보면 4원까지는 2원을 추가했을 때의 경우의 수와 동일하다가 5원을 추가했을 때부터 경우의 수가 달라진다는 것을 알 수 있다.
그 말은 추가한 금액의 동전을 threshold로 설정하고 뒤의 경우의 수가 어떤 규칙성으로 더해지는지를 확인하면 된다는 의미이다.

규칙성을 찾아보기 위해 확인을 해보면, 이전 실행에서 현재 실행이 되기 위해 더해지는 값이 n=0부터 n=5까지의 DP값이라는 것을 알 수 있다. 즉, 맨 처음 값부터 threshold까지의 값을 더해주면 된다.
이를 점화식으로 구하면 다음과 같다.

소스 코드

#include <iostream>
#include <vector>

#define MAX 10001
using namespace std;

int N,K;
int DP[MAX];
vector<int> Coin;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>K;
    Coin.resize(N+1);

    for(int i=1;i<=N;i++){
        cin>>Coin[i];
    }
    // 동전이 없는 경우의 수를 1로 설정
    DP[0]=1;

	// 입력받은 동전의 개수만큼 반복
    for(int i=1;i<=N;i++){
    	// threshold부터 목표값까지 반복
        for(int j=Coin[i];j<=K;j++){
        	// 점화식
            DP[j]+=DP[j-Coin[i]];
        	// DP[j]=DP[j]+DP[j-Coin[i]];
        }
    }
    cout<<DP[K]<<'\n';
    return 0;
}

주의할 점

처음 제출했을 때 분명 VSCode에서 코드를 실행시켰을 때는 값이 제대로 출력되었는데 메모리 초과가 되었다고 하길래 뭐 때문에 문제 조건인 4MB를 초과했는지 찾아보다가 알게 되었다.

...
int N,K;
int DP[MAX];
vector<int> Coin;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>K;
    Coin.resize(N+1);
...

정답으로 처리된 코드의 경우, Coin의 배열을 선언하고 N을 입력받은 뒤에 배열의 크기를 N+1로 선언해준다.

...
int N,K;
int DP[MAX];
vector<int> Coin(N+1);

int main(void){
    ios::sync_witsh_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>K;
...

그러나 처음 제출했던 코드의 경우, 배열의 크기를 N+1로 선언을 하고 N을 입력 받는다. 둘 다 맞는 것 처럼 보이지만, 내 생각엔 N의 값을 특정짓지 않고 크기를 선언해서 에러가 뜬 것 같다.

결과