[백준 / C++] 9084번 동전

문제 재정의 및 추상화

결론: 주어진 동전 종류로 주어진 금액을 만드는 경우의 수를 구하라

문제 접근 방식

• 작은 단위의 동전으로 해당 금액을 만드는 방법의 수는 계속 중복된다.
  -> 계속 계산하지 말고 동적 계획법의 메모이제이션을 이용하자!

해법을 찾는데 결정적이었던 깨달음

📌 dp[i] = dp[i] + dp[i - 동전 금액]

dp[i] 는 i 원을 만드는 경우의 수를 의미한다.

i원을 만드는 경우의 수는 기존의 상태에 (i - 동전 금액)원을 만드는 경우의 수를 더해나가며 구해주면 된다는 의미의 점화식이다.

이때 dp[0] = 1이다.
0원을 만드는 경우의 수는 아무 동전도 쓰지 않는 딱 하나의 경우의 수만을 갖는다.
이 dp[0]이 최초의 기존의 상태 역할을 해준다.

문제 풀이 로직

1. 테스트 케이스 개수 t를 입력받아 전체를 t번 반복한다.
2. 동전의 개수 n을 입력받는다.
3. n번 반복하며 동전의 종류를 배열에 입력받는다.
4. 만들 금액 m을 입력받는다.
5. dp[0] = 1로 초기화 해준 뒤 아래를 n번 반복한다.
   5-1. 동전 배열의 금액부터 만들 금액까지 점화식을 반복한다.
6. dp[m]을 출력한다.
   
   

문제 풀이

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m, t;
    cin >> t;
    
    while(t--){
        int dp[10001] = {0, };
        int arr[20] = {0, };
        
        cin >> n;
        
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        
        cin >> m;
        
        dp[0] = 1;
        
        for(int i = 0; i < n; i++){
            for(int j = arr[i]; j <= m; j++){
                dp[j] += dp[j - arr[i]];
            }
        }
        
        cout << dp[m] << "\n";
    }
    
    return 0;
}