[백준] 9084: 동전

0. 문제 주소

 

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

9084번: 동전

 

 

1. 풀이

 

문제에 있는 예시는 M이 너무 크므로, 다음과 같은 예시를 들어보자.

 

동전 종류 : 2, 4, 5
만들어야 하는 금액 : 10

 

기본 개념은, 첫 번째 ~ i 번째 까지의 동전을 사용했을 때, j ( 1 <= j <= M ) 원을 만들 수 있는 방법의 수를 dp 테이블에 저장할 것이다.

 

 

 

우선 첫 줄은 2원짜리 동전만 사용하여 1 ~ 10원까지의 금액을 만들 수 있는 방법으로 채웠다.

금액이 0일 때 1이 들어가 있는데, 우선 "동전을 한 개도 안 쓰면 0원을 만들 수 있다"라고 생각하고 넘어가자. 뒤에서 설명하겠다.

 

두 번째줄엔 2원, 그리고 4원을 사용하여 금액들을 만들 것이다.

 

 

 

3원 이하로는 새로 추가된 4원 짜리 동전의 영향을 받지 않기 때문에 첫째 줄과 똑같다. 4원일 때를 보자.

 

 

 

이전 상황을 기억해보자. 2원짜리 동전만을 사용하여 4원을 만들려면 2 + 2, 즉 2원짜리 2개가 필요하다. 여기서 4원짜리 동전이 추가된다면, (지금까지 0원을 만들었던 방법의 수) + (2원짜리 동전만을 사용하여 4원을 만들었던 방법의 수)의 형태로 가짓수를 구할 수 있다.

2 + 2 // 4 처럼 2가지가 실제 형태인데, 실제로 2+2 는 (2원짜리 동전만을 사용하여 4원을 만들었던 방법의 수)에 속하고, 4 는 (지금까지 0원을 만들었던 방법의 수)에 속한다. (0이라는 숫자가 나온 것은, 현재 구하고자 하는 금액 - 이번에 추가할 동전의 금액 으로 구한 것이다)

이 (0 +) 4 의 경우를 세주기 위해서 금액이 0일 때의 방법을 1이라고 정의한 것이다.

 

 

이해가 잘 안 될 수 있으니까 이번엔 8일 때를 보자.

 

 

2원짜리와 4원짜리를 사용하여 8원을 만드는 방법은 다음과 같다.

 

2 + 2 + 2 + 2

2 + 2 + 4 // 4 + 4

 

2 + 2 + 2 + 2 는 (2원짜리 동전만을 사용하여 8원을 만드는 방법)

2 + 2 , 4 는 (2원짜리와 4원짜리 동전을 사용하여 4원을 만드는 방법)

+ 4 는 (지금까지 4원을 만든 방법에 4원짜리 동전 하나를 추가시켜 8원을 만드는 과정)

 

이라고 정리할 수 있다.

 

설명하면서 그린 표처럼 2차원으로 할 필요없이, 1차원 배열로 쭉 밀어도 정상적으로 작동한다.

 

 

dp 테이블 갱신 코드는 다음과 같다.

 

for (int i=1;i<=N;i++){
	for (int j=coin[i];j<=M;j++){
		dp[j] += dp[j - coin[i]];
	}
}

 

 

 

 

2. 풀이 코드

 

* 유의할 점

1. dp[0] = 1로 미리 초기화

 

#include <bits/stdc++.h>
#define MAX 10005

using namespace std;

int T, N, M;
int coin[21];
int dp[MAX];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &T);
    for (int x=0;x<T;x++){
        memset(dp, 0, sizeof(dp));

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

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

    }
}