[Algorithm/C++] Baekjoon Online Judge 2293: 동전1 , 다이나믹 프로그래밍/배낭문제

문제 출처 : https://www.acmicpc.net/problem/9084

9084번: 동전

문제

• 우리나라 화페, 특히 동전의 단위로는 1원, 5원, 10원, 50원, 100원, 500원이 있다.
• 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다.
• (1원짜리 30개) 또는 (10원짜리 2개와 5원짜리 2개) 등의 방법이 가능하다.
• 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램 작성

입력

• t : 테스트 케이스 개수
• n : 동전의 가지수 ( 1<=n<=20 )
  • 동전의 각 금액이 오름차순으로 정렬되어 주어짐 ( 1 원 <=Cn​<=10000 원 )
• m : 동전으로 만들어야 하는 금액 ( 1<=m<=10000 )

 

풀이 방법

이긴한데 여러 풀이를 참조한..

 

이 문제는 배낭 문제의 확장편이라고 하기엔 최대 가치를 계산해야하는 것도 아니고 가치가 따로 있는게 아니었기 때문에 알고리즘을 생각해내는데 큰 어려움을 겪었다.

 

1, 2, 4원으로 6원을 만든다고 가정하자.

그러면 6원을 만들 수 있는 방법의 수는 다음과 같다.

 

• 1원을 6개 사용함 : 1가지
• 2원과 4원을 사용함 : 1가지
• 1원 두개(결국 2원)와 4원을 사용함: 1가지 
• 2원을 3개 사용함 : 1가지

 

마지막 1번째와 4번째 방식을 유심히 살펴보면 단계가 2원을 사용해서 4원을 만들고, 또다시 4원과 2원을 사용해서 6원을 만든다.

 

여기서 이런 점화식을 얻을 수 있다.

dp[i] = dp[i] + dp[i-현재 동전의 액수] 
// 2원으로 4원을 만든다고 생각하면 기존에 4원을 만들었던 방법의 수 + 2원을 만드는 방법의 수가 4원을 만드는 방법의 수이다.

 

이 점화식에서 현재 동전의 액수가 i 와 동일하다고 생각하면 dp[i] = dp[i] + dp[0]이 된다. 따라서 현재 동전의 액수가 i인 경우엔 1가지의 방법을 더해야하기 때문에 dp[0] = 1로 초기화해야 한다.

 

최종 코드는 다음과 같다.

#include <iostream>
#define N_MAX 101
#define K_MAX 10001

using namespace std;

int dp[K_MAX] = {1,};
int arr[N_MAX] = {};
int N, K;
int dp_func(){
    for (int i = 0; i < N; i++) { //각 동전에 대해
        for (int j = arr[i]; j <= K; j++) {
            dp[j] +=dp[j - arr[i]];
        }
    }
    return dp[K];
}
int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    cout<<dp_func() << "\n";
    return 0;
}