백준 2293 동전 1

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

2293번: 동전 1

 

 

 

CODE

 

예를 가지고 보자,

예제 입력

3 10
1
2
5

1, 2, 5원을 가지고 10원을 만들어야 한다.

 

10원을 만들 때 마지막으로 사용한 값이 1이면,

9원에서 1원을 추가해서 10원이 만들어진 것이다.

즉, 10원을 만들 수 있는 경우의 수는 9원을 만들 수 있는 경우의 수를 포함한다.

 

10원을 만들 때 마지막으로 사용한 값이 2이면,

8원에서 2원을 추가해서 10원이 만들어진 것이다.

즉, 10원을 만들 수 있는 경우의 수는 8원을 만들 수 있는 경우의 수를 포함한다.

 

10원을 만들 때 마지막으로 사용한 값이 5이면,

5원에서 5원을 추가해서 5원이 만들어진 것이다.

즉, 10원을 만들 수 있는 경우의 수는 5원을 만들 수 있는 경우의 수를 포함한다.

 

dp[10] = dp[9] + dp[8] + dp[5]

 

즉, j원을 만들 수 있는 경우의 수는 가지고 있는 모든 동전에 대해서 (j - (어떤 동전))원 만들 수 있는 경우의 수 모두를 더한 것이다.

 

따라서 K원을 만들 수 있는 경우의 수를 구하기 위해서는 이전의 값을 만들 수 있는 모든 경우의 수가 필요하므로,

가지고 있는 모든 동전에 대해서 1원부터 만들 수 있는 경우의 수를 구하면서 dp를 활용해 K원에 대해서 까지 구하면 된다.  

 

base:

dp[0] = 1로 두는데, 이는 아무 동전도 선택하지 않은 상태에서 어떤 동전을 더해서 그 동전 값을 구하는 것은 1가지 경우를 의미하기 때문이다.

아무 동전도 선택하지 않은 경우도 하나의 경우의 수.

dp[0] = 1;    //base: 아무 동전도 선택하지 않은 경우
for (int i = 0; i < N; i++) {    

    //각 j에 대해서 동전을 적당히 사용해서, 그 가치의 합이 j원이 되는 경우의 수 구하기.
    //이를 통해, 결국에 그 가치의 합이 K원이 되는 경우의 수를 구할 수 있다.
    for (int j = arr[i]; j <= K; j++) { 
        dp[j] += dp[j - arr[i]];    
    }
}

 

위의 예제 입력에 대한 풀이를 시각화 해보자.

먼저 동전 1에 대해서 10원을 만드는 경우의 수를 계산해준다.

1(=j)부터 10(=k)까지 dp[j] += dp[j - 1] 을 해준다.

 

동전 2에 대해서는 0원과 1원은 만들지 못하니 패스하고

j = 2부터 10(=k)까지 dp[j] += dp[j - 2] 를 해준다.

 

마찬가지로 동전 5에 대해서는 0~4원을 만들지 못하니 패스하고

j = 5부터 10(=k)까지 dp[j] += dp[j - 5] 를 해준다.

dp[10] = 10

 

 

 

참조: https://danidani-de.tistory.com/5

 

EXPLANATION

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> arr(N);
    vector<int> dp(K+1);
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    dp[0] = 1;    //base: 아무 동전도 선택하지 않은 경우
    for (int i = 0; i < N; i++) {    
        for (int j = arr[i]; j <= K; j++) { 
            dp[j] += dp[j - arr[i]];    
        }
    }

    cout << dp[K] << "\n";
    return 0;
}