알고리즘13 :: BOJ_2293_동전1

DP가 어렵다고 느끼는 이유는 점화식을 세워야 한다. 이 문제는!!

DP를 연습하기 좋은 문제지 않나 생각해본다. 위 두 블로그를 통해서 방법은 같지만 서로 다른 점화식을 확인할 수 있었다. 

요약하자면 다음과 같다. 

 

문제에서는 k원이라고 주어졌지만, 테스트 케이스 10원으로 예시로 든다면

1원 부터 테스트 케이스(원) 까지 만들 수 있는 방법을 전부 고려해보는것이 가장 첫 번째 스텝인것 같다. 

이때 입력으로 주어진 동전을 고려해 봐야 하는데 테스트 케이스로 주어진 1원, 2원 그리고 5원을 고려해보자.

 

1원으로 1~10원을 만들 수 있는 방법은 각각 1원은 1가지 방법 2원도 1가지 방법 ... 10원도 한가지 방법이다. 

1원으로 뭔 짓을 해봤자 1가지 방법밖에 나올 수 없다. 

 

2원으로 1~10원을 만들 때는 1원은 만들 수 없다. 왜냐하면 작아서

1원과 2원의 조합 혹은 2원으로 만들 수 있는 패턴을 찾아봐야 한다. 

1원과 2원의 조합 혹은 2원으로 만들 수 있는 패턴을 2~10원을 만들 경우의 수를 모두 찾아보자.

1 1, 2 두가지이다. 

 

3원도 계산해보자. 1 1 1 / 1 2  = 2가지

4원도 계산해보자. 1 1 1 1 / 1 1 2(=2 1 1) / 2 2  = 3가지

5원도 계산해보자. 1 1 1 1 1 / 1 1 1 2 / 1 2 2 = 3가지

 

이렇게 하면 표를 하나 만들 수 있다. 

(0을 만들 수 있는 경우는 1가지 인데, 표에 담지 않았다.)

우리가 만들 k원 => 1 2 3 4 5 6 7 8 9 10

입력으로 받은 1원   1 1 1 1 1 1 1 1 1 1

입력으로 받은 2원   1 2 2 3 3 4 4 5 5 6

입력으로 받은 5원   1 2 2 3 4 5 6 7 8 10 

 

보라색으로 칠한 부분은 변하지 않는다. x로 칠려했으나 규칙을 찾아보기 위해 표시하였다.

이럴 경우 점화식이 두개가 나온다. 

 

다음 입력 받는 동전이 더큰 경우 이전에 동전에서 구한 k원을 구한 방법을 그대로 따른다. (보라색 표시)

그리고, 눈치 챘는지 모르지만 입력받은 2원의 경우에는 2원에서 값이 변하고 입력받은 5원의 경우에는 5원에서 값이 변한다. 

입력받은 동전이 2원일때 k가 4인 값을 구하고 싶으면 빨간색 부분 두개를 더하여 파란색 부분을 구하면 된다.

 

이차원 배열로 나타내면, (1부터 시작, 표의 가로 1~k, 동전 값 : n)

M[n][k] = M[n][k-n]+M[n-1][k] (n<=k)

M[n][k] = M[n-1][k] (n>k) 

예를들면 M[2][4](=3) = M[1][4] + M[2][4-2] 가된다.

실질적으로 위와 같은 방법은 메모리 초과가 난다고 한다. 

 

두번째로 찾아본 점화식은 아래와 같다.

M[k]+=M[k-arr[i]] 이다.(* M[0] = 1)

이렇게 쓰면 무척 애매하기 때문에 sudo code로 작성해보면 아래와 같다.

for(int i = 1; i<=n; i++) //n은 입력받은 동전의 수가 되고

for(int j=arr[i]; j<=k; j++) 

M[j]+=M[j-arr[i]]; //arr[i]의 값은 n의 개수만큼 입력받아 저장되어 있다.

가 된다. 첫번째 for문은 위의 표에 세로가 되고 두번째 for문은 위의 표에 가로라고 볼 수 있다. 

이 점화식도 마찬가지로, n>k 인경우에는 M[n-1][k] 의 값을 그대로 쓰고 그렇지 않으면 값을 더하는데 

중복을 배제하기 때문에 처음에는 1~k까지 그다음에는 2~k까지 .... k-1~k 까지 계산해서 마지막에 k의 값을 얻을 수 있다. 

 

손으로 직접 그려보면 두가지 다 위와 같은 표가 나오는것을 확인할 수 있다.  

 

(두번째 출력결과는 무시)

 

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n, k, temp;
    cin>>n>>k;
 
    int arr[101], DP[10001];
    memset(arr, false, sizeof(arr));
    memset(DP, false, sizeof(DP));
    
    for(int i=0; i<n; i++)
        cin>>arr[i];
        
    DP[0] = 1;
    for(int i=0; i<n; i++){
        for(int j=arr[i]; j<=k; j++){
            DP[j] += DP[j-arr[i]];
            cout<<"DP : "<<DP[j]<<" ";
        }
        cout<<" "<<arr[i]<<"만큼 밀립니다";
        cout<<endl;
    }
    
    cout<<DP[k]<<endl;  
}