IF - 동전교환

문제

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

예시

exchange	coinKind	answer
15	[1,2,5]	3

설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

풀이 및 회고

• 상수인 exchange 의 값만큼을 길이로 갖는 빈 배열 dy를 만든다.
• dy 의 각 인덱스는 잔돈n원을 의미하고, 원소는 잔돈이 n원 일 때 거슬러 줄 최소 동전의 갯수를 의미한다.
• 예로, 잔돈이 0원이면 거슬러 줄 동전이 없다. 따라서 dy[0] = 0
• 잔돈이 5원일 경우의 최소 동전의 개수는 잔돈이 [5-1, 5-2, 5-5]원일 경우의 최소 동전의 개수에서 1을 늘린 값 중 최소값이다.
• 즉, 거슬러줄 돈 5원에서의 동전 개수의 최소값은 0원에서 5원짜리 동전 하나만 추가된 1개이다.
• 문제에선 거스름돈 15원이 주어졌으므로 잔돈이 [15-1, 15-2, 15-5] 원일 경우의 최소 동전의 개수에서 1을 늘린 값이 곧 답이다.

코드

const solution = (coinKind, exchange) => {
	let answer = 0;
	const dy = Array.from({ length: exchange + 1 }, () => 1000);
	dy[0] = 0;

	for (let i = 1; i <= coinKind.length; i++) {
		for (let j = coinKind[i]; j <= exchange; j++) {
			dy[j] = Math.min(dy[j], dy[j - coinKind[i]] + 1);
		}
	}
	answer = dy[exchange];
	console.log(answer);
	return answer;
};