[C++] 동전 (9084번)

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

9084번: 동전

---

문제풀이

역시 dp문제.. 풀때마다 새롭고 풀때마다 머리아프다.

나만의 방법을 좀 터득했다면, 일단 이차원 배열로 만들어 생각해 보는것이다.

처음 예제를 예로 들어보자.

1, 2 원짜리 동전이 있다. 행을 동전, 열을 총 금액이라고 보고 표를 보자.

 

주의할점이 하나 있는데, 동전 1 2 와 2 1은 하나로 취급해야 한다.

	1	2	3	4	5	6	7	8	9
1	1	1	1
2	1	2	3

생각해보자. 열 순서대로 표를 읽어볼 것이다.

1원 칸에서 1원은 1원동전으로 만들 수 있으니 1이다. (1)

2원 칸에서 1원은 1원동전으로 만들 수 있으니 1이다. (1)

 

1원 칸에서 2원은 1원동전으로 만들 수 있으니 1이다. (1 1)

2원 칸에서 2원은 1원 동전으로 만들 수 있고, 2원 동전으로 만들 수 있으니 2다. (1 1, 2)

 

1원 칸에서 3원은 1원동전으로 만들 수 있으니 1이다. (1 1 1)

2원 칸에서 2원은 1원 동전으로 만들 수 있고, 2원 동전으로 만들 수 있으니 2다.  (1 1 1, 1 2)

 

규칙이 보인다.

2원동전 행에는 1원 동전과 2원동전을 사용한 경우의 수가 누적으로 구해지는 것이 보인다.

즉 점화식이 나오게 되는데, arr[i][j] = arr[i-1][j] + arr[i][j-coins[i]] 가 된다.

coins는 배열이고 [1, 2](동전)가 저장되어있다.

	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
2	1	2	3	3	4	4	5	5	6

이렇게 하면 구할 수있다.

인덱스 헷갈리는거에 주의하고, 각 행별로 금액에 맞는 위치는 1로 지정해두는 것을 잊지말자.

 

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int coins[n];
        for(int i=0; i<n; i++) cin >> coins[i];
        int target;
        cin >> target;
        long long arr[n][target+1];

        for(int i=0; i<n; i++) {
            for(int j=0; j<=target; j++) {
                if(coins[i] - j == 0) arr[i][j] = 1;
                else arr[i][j] = 0;
            }
        }

        for(int i=0; i<n; i++) {
            for(int j=1; j<=target; j++) {
                if(i != 0) arr[i][j] += arr[i-1][j];
                if(j-coins[i] > 0) arr[i][j] += arr[i][j-coins[i]];
            }
        }
        cout << arr[n-1][target] << "\n";
    }
    return 0;
}