[백준 9084] 동전(C++)

동전

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

문제 해결 과정

1. 문제를 읽고 이해하기

테스트 케이스의 개수 T (1 <= T <= 10)

동전 종류의 수: N (1 <= N <= 20)

만들어야 하는 금액: M (1 <= M <= 10000)

N가지의 동전을 가지고 M을 만들어야 한다.

 

만약 10원과 20원을 가지고 50원을 만드는 경우의 수는 3가지가 있다.

1. 10 10 10 10 10

2. 10 10 10 20

3. 10 20 20

2. 재정의와 추상화

N 개의 수를 사용하여 어떤 수 M를 만들 수 있는 경우의 수를 구해야 한다.

3. 계획 세우기

각 상황에 대한 모든 경우의 수를 나열하다보면 감을 잡을 수 있다. 

10과 20으로 50을 만드는 경우의 수

10원과 20원으로 50원을 만드는 경우의 수를 다시 확인해보자

1. 10 10 10 10 10

2. 10 10 10 20

3. 10 20 20

각 경우의 수를 어떻게 효율적으로 도출할 수 있을까?

 

10을 사용한 개수를 보면 각각 5개, 3개, 1개이다.

2번째, 3번째에서 20을 사용하는 경우를 보자.

10 10 10 (20) -> 30을 만드는 경우에 20을 더한다.

10 (20 20) -> 10을 만드는 경우에 20 * 2를 더한다. 

이 경우를 다르게 바라보면 (10 20) 20 으로 30을 만드는 경우에 20을 더한 경우으로 볼 수 있다.

 

30을 만드는 경우의 수를 살펴보자.

1. 10 10 10

2. 10 20

30원을 만들기 위해 필요한 것은 10원을 만드는 경우의 수와 20원을 만드는 경우의 수이다.

10 10 (10) -> 20을 만들기 위한 경우의 수

10 (20) -> 10을 만들기 위한 경우

 

이처럼 Bottom Up DP를 통해 쉽게 접근할 수 있다.

만들려 하는 값 M에 더하려는 값(코인)의 크기를 뺀 경우를 알 수 있다면 M의 경우의 수를 구할 수 있다.

그림을 통해 확인해보자.

1원과 2원으로 4원을 만드는 테스트케이스

4원을 만들 수 있는 경우의 수는 3임을 확인할 수 있다.

5원과 7원으로 22를 만드는 테스트 케이스

22원을 만드는 경우의 수는 1임을 확인할 수 있다.

4. 계획 검증하기

테스트 케이스의 개수 T (1 <= T <= 10)

동전 종류의 수: N (1 <= N <= 20)

만들어야 하는 금액: M (1 <= M <= 10,000)

시간제한: 1s (연산 1억회)

 

각 동전을 통해 M을 만드는 경우의 수를 모두 구해야 하기 때문에 하나의 테스트케이스가 대략적으로 O(NM)의 시간 복잡도를 가진다.

최악의 경우 200,000 * 10(T)의 연산횟수를 가진다.

코드

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T, N, target;
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 0; i < N; ++i) {
            cin >> coins[i];
        }
        cin >> target;
        bzero(dp, sizeof(dp));
        dp[0] = 1;
        for (int i = 0; i < N; ++i) {
            int coin = coins[i];
            for (int j = coin; j <= target; ++j) {
                dp[j] += dp[j - coin];
            }
        }
        cout << dp[target] << '\n';
    }
}

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.