Beakjoon 2293 동전1

13 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/2293

나의 풀이

먼저 DP는 다음과 같이 정의한다.
DP[i] = 동전 가치의 합을 i로 만들 수 있는 경우의 수

예를 들어 n=3, k=10, 각각의 동전이 나타내는 가치 coin = {2, 1, 5}일 때
2원의 동전을 1개 이상 사용하여 동전 가치의 합을 i로 만들 수 있는 경우의 수와 DP[i]는 다음과 같다.

coin\i	0	1	2	3	4	5	6	7	8	9	10
2	0	0	1	0	1	0	1	0	1	0	1
DP	1	0	1	0	1	0	1	0	1	0	1

이 때 구한 DP는 오직 2원 동전 만 사용한 경우를 구한 것이다.
먼저 동전 가치의 합을 0으로 만드는 경우 2원의 동전을 하나도 사용하지 않지만 모든 상황에서 오직 한가지만 존재하기 때문에 DP[0] = 1로 고정한다.

2원의 동전만 사용하여 i로 만드는 경우를 구할 때 경우의 수는 DP[i-2]의 경우의 수와 같다 왜냐하면 DP[i-2]의 경우 2원의 동전을 사용하여 i-2원을 만들 수 있는 경우의 수를 의미하고 i-2원에 2원의 동전 하나를 추가하면 결국 i로 만들 수 있기 때문이다.
위 방식으로 모든 DP를 구해보자
DP[1] = DP[1-2] 이다. 동전이 음수인 경우는 항상 불가능 하기 때문에 DP[1] = 0이다.
DP[2] = DP[0] = 1 —> 이 의미는 0을 만드는 한가지 경우에 2 동전 하나를 추가하는 것이다.
DP[3] = DP[1] = 0 —> 동전 1원을 만드는 경우가 없기 때문에 동전 2원을 추가하여 3을 만들 수도 없다.
DP[4] = DP[2] = 1 —> 동전 2를 만드는 경우에 2원의 동전 하나를 추가한다.
…..
DP[10] = DP[8] = 1

다음으로 1원의 동전을 1개 이상 사용한 경우를 포함하여 표현하면 다음과 같다.

coin\i	0	1	2	3	4	5	6	7	8	9	10
2	0	0	1	0	1	0	1	0	1	0	1
1	0	1	1	2	2	3	3	4	4	5	5
DP	1	1	2	2	3	3	4	4	5	5	6

이 때 DP를 업데이트하기 전 값은 2원의 동전만 사용하여 구한 DP값이고 새로 구한 DP는 동전 1과 동전 2를 사용한 경우를 구한 것이다.
이 경우도 위에서 구한 방식과 마찬가지로 진행할 수 있지만 기존 2원 동전만 사용한 경우에 추가적으로 1원 동전을 1개 이상 사용한 경우도 더해주어야 하기 때문에 DP[i] = DP[i] + DP[i-1]로 표현할 수 있다.
DP[1] = DP[1] + DP[1-1] = 0 + 1 —> 동전 1과 2를 사용하여 1을 만드는 경우는 2원의 동전만 사용해서 1을 만든 경우와 1과 2원을 이용하여 0원을 만드는 경우에서 1원을 추가하여 만드는 경우를 합친 값과 동일하다.
DP[2] = DP[2] + DP[1] = 1 + 1 —> 동전 1과 2를 사용하여 2를 만드는 경우는 2원의 동전만 사용해 2를 만든 경우와 1과 2를 모두 이용하여 1원을 만드는 두 경우를 합치면 된다.
같은 방식으로 DP를 구하면 DP[10] = DP[10] + DP[9] = 1 + 5 = 6

마지막으로 5원의 동전을 1개 이상 사용한 경우를 포함하여 표현하면 다음과 같다.

coin\i	0	1	2	3	4	5	6	7	8	9	10
2	0	0	1	0	1	0	1	0	1	0	1
1	0	1	1	2	2	3	3	4	4	5	5
5	0	0	0	0	0	1	1	2	2	3	4
DP	1	1	2	2	3	4	5	6	7	8	10

이 때 DP를 업데이트 하기 전 값은 1원과 2원 동전을 사용하여 구한 DP 값이고, 새로 구한 DP는 동전 1, 2, 5를 사용하여 구한 것이다.
같은 방식으로 DP를 구하면
DP[1] = DP[1] + DP[1-5] = 1 + 0
….
DP[5] = DP[5] + DP[0] = 3 + 1
…
DP[10] = DP[10] + DP[5] = 6 + 4 = 10으로 동전 1, 2, 5를 사용하여 k(10)을 만들 수 있는 경우의 수는 10이다.

풀이 코드 : 2293 동전1

#include <iostream>
#include <vector>

using namespace std;

int DP[10001];

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

    int n, k, num;
    cin>>n>>k;

    vector<int> coin; 
    for(int i=0;i<n;i++){
        cin>>num;
        coin.push_back(num);
    }

    DP[0] = 1;

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

    cout<<DP[k];
}

채점결과