IF - 동전 교환

문제

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

예시

Input	Input	Output
[1,2,5]	15	3

풀이 및 회고

• 주어진 배열 coinTypes의 원소들로 주어진 금액 amount 를 만든다고 했을 때, 가장 적은 수의 원소를 사용하는 경우를 구하는 문제이다.
• DFS 함수 내에서 coinTypes 배열을 돌면서 깊이와 sum에 coninTypes의 i번째 원소를 더해 내려보낸다.
• sum 이 주어진 amount보다 커진다면 현재 깊이에서의 DFS를 끝낸다.
• sum이 주어진 금액 amount와 같아지면 DFS 의 깊이 depth가 곧 금액 amount를 만드는 데에 쓰인 동전의 개수이다.
• depth가 이전에 정해진 answer 보다 같거나 크다면 answer의 최소값을 구하고자 하는 문제의 의도와 다르므로, 현재 깊이에서의 DFS를 끝낸다.
• Cut-Edge 를 처음 써봤는데, 시간복잡도가 획기적으로 줄지만 코드 자체는 한 줄 밖에 되지 않는다는 점이, 역시 제일 좋은 코드는 짧더라도 임팩트가 강한 코드가 아닌가 싶다.

코드

const solution = (coninTypes, amount) => {
	let answer = Number.MAX_SAFE_INTEGER;
	const DFS = (depth, sum) => {
		if (sum > amount) return;
		if (depth >= answer) return;
		if (sum === amount) {
			answer = Math.min(sum, depth);
			return;
		} else {
			for (let i = 0; i < coninTypes.length; i++) {
				DFS(depth + 1, sum + coninTypes[i]);
			}
		}
	};

	DFS(0, 0);
	return answer;
};