[BOJ] 백준 2293번: 동전 1

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

2293번: 동전 1

---

문제

n개의 동전의 가치가 주어질 때 동전을 원하는 대로 사용하여 k원을 만드는 경우의 수를 구하는 문제입니다. 동적 계획법 관련 문제들에서 이 문제와 유사한 문제들이 가끔 출제되며 이 문제를 잘 이해하고 풀면 0/1 배낭 문제 또한 쉽게 풀 수 있습니다.

 

---

풀이

쉽게 접근해 보기 위하여 dp [i][j]를 0~i 번째 동전을 사용하여 j원을 만들 때 적어도 한 개의 i번째 동전을 사용하는 경우의 수로 생각해 봅시다. 아래의 예제에 대하여 dp [i][j]를 모두 채워보도록 하겠습니다. i 번째 동전의 가치는 coin [i]에 저장합니다.

예제 1번

초기 배열은 아래와 같이 초기화 할 수 있겠네요. 

초기 dp 배열

0원을 만드는 경우의 수는 0개의 동전을 선택하는 방법이므로 1가지입니다.

그럼 먼저 dp[0][1~10] 의 배열은 아래와 같이 채울 수 있습니다. 1원으로 각 금액을 만드는 경우는 1원만 사용하는 경우의 1가지 이니까요. 이때 점화식은 dp [0][j] = dp [0][j-coin [0]] = dp [0][j-1]로 할 수 있겠네요.  

0번째 동전인 1원으로 1~10원을 만드는 경우의 수를 채운 결과

이제 1번째 동전인 2원으로 그 다음 배열을 채울 차례입니다. 먼저 앞서서 dp [i][j]는 0번째 동전부터 i 번째 동전까지 사용하여 j원을 만드는 경우의 수를 저장한다고 했습니다.

2원 동전을 사용해서 0원을 만드는 경우는 2원 동전을 사용하지 않는 경우의 수 이므로 1가지이지만, 이 경우의 수는 앞선 1원 동전에서 사용되었기 때문에 예외적으로 0의 값을 갖습니다. (dp [0][0]을 제외한 모든 dp [i][0]은 0이 됩니다.) 또한, i번째 동전의 가치보다 적은 금액의 dp [i][0~j]의 경우의 수는 전부 0의 값을 갖습니다 (j < coin [i]). 아래 그림은 이 조건에 따라 채워진 결과입니다.

두번째 과정

 

나머지 배열을 채우기 위해, 먼저 우리는 첫 번째 동전의 점화식이 dp [0][j] = dp [0][j-coin [0]]이라는 것과 dp [i][j]를 0번째 동전부터 i번째 동전을 사용하되 i번째 동전을 적어도 한 개 사용하는 경우의 수로 정의한 사실을 다시 한번 기억하고 넘어갑시다.

위의 그림에서 dp [1][2]는 0번째와 1번째 동전을 사용하되 2원 동전을 적어도 하나 이상 사용하여 2원을 만드는 경우의 수 이므로, 0번째 동전만 사용해서 0원을 만드는 경우 dp [0][0]와 1번째 동전을 하나 이상 사용해서 만드는 경우 dp [1][0]의 합인 1 이 됩니다. 

dp [1][3]은 같은 원리로 dp [0][1] + dp [1][1] = 1의 값으로 계산되며, dp [1][4]는 dp [0][2] + dp [1][2] = 2가지 경우가 있습니다. 이 규칙으로 두번째 줄까지 구해보면 아래와 같습니다.

 

이렇게 계산해나가다 보면 우리는 dp 배열을 2차원로 선언 할 필요가 없음을 알 수 있습니다 (1차원 배열이면 충분합니다). i원 동전을 사용하여 j 원을 만들때는 j - coin[i] 금액의 누적 합만 알면 되기 때문이죠.

점화식

실제로 이렇게 풀어야 문제에 주어진 메모리 제한 조건을 만족할 수 있습니다.

위, 1차원 배열 풀이, 아래, 2차원 배열 풀이 결과

 

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
typedef long long ll;

int n, m;
int arr[101];
int dp[10001] = { 0, };
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = arr[i]; j <= m; j++) {
			if (dp[j - arr[i]]) {
				dp[j] += dp[j-arr[i]];
			}
		}
	}
	cout << dp[m];
}