[백준] 9084번*

💻 C++ 기반

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

1. 테이블 정의하기
dp[i] : 주어진 동전으로 i 금액을 만들 수 있는 방법의 수


2. 점화식 찾기
동전이 1원, 2원이 있을 때의 과정을 직접 생각해보자.
i = 1일 때:
1
-> dp[1] = 1

i = 2일 때:
1 + 1
2
-> dp[2] = 2

i = 3일 때:
1 + 1 + 1
2 + 1
-> dp[3] = 2

i = 4일 때:
1 + 1 + 1 + 1
2 + 1 + 1
2 + 2
-> dp[4] = 3

💡 뭔가 dp[i] = dp[선택한 동전의 금액] + dp[i - 선택한 동전의 금액] 과 같은 규칙이 보이는 것만 같다.
그러나 i = 4일 때 위의 점화식을 적용하면 2 + 1 + 1, 1 + 2 + 1 이렇게 두 가지 경우가 중복된다.
어떻게 해결할 수 있지?

저렇게 결과적인 dp값을 서로 더하지 말고,
턴을 여러 번 돌면서 dp값을 더해보자

예를 들어, 첫 번째 동전을 선택할 때의 dp[1]부터 dp[i] 값을 먼저 구하고,
두 번째 동전을 선택할 때의 dp[1]부터 dp[i] 값을 두 번째 턴에 구하는 것이다.

그러면 아래와 같이 과정이 바뀐다.

첫 번째 동전을 선택할 때:
dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 1

두 번째 동전을 선택할 때:
dp[1] = 1
dp[2] = dp[2] + dp[0] = 2
dp[3] = dp[3] + dp[1] = 2
dp[4] = dp[4] + dp[2] = 3

dp[4] 값이 제대로 나오는 것을 확인할 수 있다.


3. 초기값 정하기
dp[0] = 1

#include <cstdio>

#define MAX_PRICE 10001

using namespace std;

void sol(int dp[], int N, int cost[], int M)
{
    dp[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        for (int j = cost[i]; j <= M; j++)
        {
            dp[j] += dp[j - cost[i]];
        }
    }
    printf("%d\n", dp[M]);
}

int main()
{
    int T;
    scanf("%d", &T);

    for (int i = 0; i < T; i++)
    {
        int N;
        scanf("%d", &N);

        int cost[N + 1];
        for (int j = 1; j <= N; j++)
        {
            scanf("%d", &cost[j]);
        }

        int M;
        scanf("%d", &M);

        int dp[MAX_PRICE] = {
            0,
        };
        sol(dp, N, cost, M);
    }
    return 0;
}