동전 2

문제

백준 2294번 - 동전 2

언어

JavaScript

순서도

점화식을 정의하고, 그에 맞게 dp 배열 생성하기
dp 배열의 base 값 정의
점화식과 base 값을 이용해서 dp 배열 채우기
dp[k] 값 출력

문제 풀이 step 1

n 가지 종류의 동전이 있습니다.
이 동전들을 적당히 사용해서 그 가치의 합이 k 원이 되도록 만듭니다.
단, 동전의 개수를 최소로 사용해야 합니다.
이 때의 동전의 개수를 출력하는 문제입니다.

문제 풀이 step 2

우선, 중복을 제거한 동전의 종류를 구합니다.
- 문제에서 n 가지 종류의 동전이 주어진다고 했으나, 같은 동전이 여러 번 주어질 수 있다고 했습니다.
- 따라서, 주어진 n 가지 종류의 동전에서 중복을 제거합니다.

문제 풀이 setp 3

dp[k] = n 가지 종류의 동전으로 k 원을 만들 때, 동전의 최소 개수
DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
점화식은 “dp[k] = Math.min(dp[k], dp[k - coin[j]] + 1)” 입니다.
- 단, i - coin[j] >= 0 이고, dp[i - coin[j]] !== -1 이여야 합니다.
dp 배열은 모두 -1 로 초기화 합니다.
- 주어진 동전으로 만들 수 없는 k 인 경우에는 -1 을 출력해야 하기 때문입니다.
base 값은 0 입니다.
- 0 원을 만들 수 있는 방법의 수는 0 이기 때문입니다.
우선, 점화식과 base 값을 이용해서 dp 배열을 다 채웁니다.
예를 들어 dp[k] 를 구하려고 할 때,
- 주어진 n 개의 동전을 모두 확인합니다. (실제는 중복 제거 이후이므로 n 이하 개)
- dp[k] === -1 이면, dp[k] = dp[k - coin[j]] + 1 입니다.
- dp[k] !== -1 이면, dp[k] = Math.min(dp[k], dp[k - coin[j]] + 1) 입니다.
- 위의 두 경우를 통해서 주어진 동전을 다 사용해가면서, 모든 경우를 검사해보고, 그 중에서 동전의 개수가 최소가 될 때, 그 값이 dp 값이 됩니다.
추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	let [n, k] = input[0].split(" ").map(Number);
	// 중복된 동전 제거
	const coin = [...new Set(input.slice(1, n + 1))]
		.map(Number)
		.sort((a, b) => a - b);

	n = coin.length;

	const dp = Array.from({length: k + 1}, () => -1);
	// base
	dp[0] = 0;

	for (let i = 1; i < k + 1; i++) {
		// n 개의 종류의 동전을 다 확인해보면서
		for (let j = 0; j < n; j++) {
			if (i - coin[j] < 0 || dp[i - coin[j]] === -1) continue;

			// 점화식을 적용
			if (dp[i] === -1) dp[i] = dp[i - coin[j]] + 1;
			else dp[i] = Math.min(dp[i], dp[i - coin[j]] + 1);
		}
	}

	return dp[k];
};

console.log(solution(input));