[BOJ_9084_RN] 동전 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/9084

문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming )

해설

이 문제는 간단한 동적계획법으로 해결이 된다. 아이디어는 간단하다. 동전을 순차적으로 고를 때 각 동전마다 몇개씩 고를지 계산하면 된다.

N개의 동전종류가 남았을 때 M원을 만들 수 있는 경우의 수를 DP[N][M] 이라고 가정하고 부분문제로 나누면

동전 종류가 N - 1개가 남았고 현재 동전을 1개 선택한 경우

동전 종류가 N - 1개가 남았고 현재 동전을 2개 선택한 경우

...

모든 경우의수의 합이 정답이 된다.

따라서 위의 점화식을 얻게 된다.

시간복잡도

DP테이블을 다 채우는데는 N * M의 시간복잡도를 가진다. 또 find함수 내부에서 돌아가는 반복문은 최대 M번 반복한다. 그래서  라는 시간복잡도가 나오게 되지만 M번을 다 채워서 반복하지 않기 때문에 시간 내에 해결이 가능하다.

동전 코드 [ C ]

#include <string.h>
#include <stdio.h>
int ar[21], dp[21][10001];
int max(int i, int j) {
	return i > j ? i : j;
}
int find(int n, int m) {
	if (m < 0) return 0;
	else if (!m) return 1;
	else if (n < 0) return 0;
	else if (dp[n][m] != -1) return dp[n][m];
	int i;
	dp[n][m] = 0;
	for (i = 0; i * ar[n] <= m; ++i) {
		dp[n][m] += find(n - 1, m - i * ar[n]);
	}
	return dp[n][m];
}
int main() {
	int t;
	scanf("%d", &t);
	for (; t--; ) {
		memset(dp, -1, sizeof dp);
		int i, j, n, m;
		scanf("%d", &n);
		for (i = n; i--; ) {
			scanf("%d", ar + i);
		}
		scanf("%d", &m);
		printf("%d\n", find(n - 1, m));
	}
	return 0;
}