거스름돈

문제

언어

  • JavaScript

순서도

  1. n 원에서 5 원의 비중을 최대한 높이고, 나머지는 2 원으로 채우기

문제 풀이 step 1

  • 주어진 n 원에 대해서 2 원과 5 원으로 거스름돈을 주려고 할 때, 동전의 개수를 최소로 만든 경우의 동전의 개수를 구하는 문제입니다.

문제 풀이 step 2

  • 본 문제는 그리디 방식으로 풀 수 있습니다.
  • 거스름돈의 동전의 개수가 최소가 되려면 거스름돈을 최대한 5 원으로 구성해야 합니다.
  • 따라서, 우선 n 원에 대해서 최대한 5 원으로 거스름돈을 구성하고, 나머지를 2 원으로 구성하면 됩니다.
  • 이 때, 나머지가 2 원으로 구성되지 않는다면, 5 원에서 한 개씩 빼서 나머지에 더한 후 2 원으로 구성하면 됩니다.
  • 만약 5 원의 개수가 0 이 되어도, 나머지가 2 원으로 구성할 수 없다면 -1 을 출력합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

const solution = (input) => {
	const n = Number(input[0]);

	// 최대한 5 원의 함량 높이기
	let [five, remains] = [parseInt(n / 5), n % 5];

	while (five > 0) {
		// 나머지를 2 원으로 구성할 수 있는 경우
		if (remains % 2 === 0) return five + remains / 2;

		// 나머지를 2 원으로 구성할 수 없다면 5 원을 하나 빼서 나머지에 더하기
		[five, remains] = [five - 1, remains + 5];
	}

	// 만약 5 원의 함량이 0 이 되어도, 나머지를 2 원으로 구성할 수 없다면, -1 출력
	return remains % 2 === 0 ? remains / 2 : -1;
};

console.log(solution(input));

다른 방식의 문제 풀이

  • 본 문제는 다이나믹 프로그래밍 기법으로도 풀 수 있습니다.
  • 2 차원으로 2 원으로만 구성하는 경우, 2 원과 5 원으로 구성하는 경우로 dp 배열을 구성하면 됩니다.
  • 간단하게 소스코드에 주석으로 설명하겠습니다.

소스코드

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

const solution = (input) => {
	// 최소값 비교를 간단하게 하기 위해서 -1 대신 MAX 값을 사용했습니다.
	const MAX = Number.MAX_SAFE_INTEGER;

	const n = Number(input[0]);

	const dp = [];
	// base
	// 2 원과 5 원을 사용하는 경우 비교를 좀 더 간단하게 하기 위해서 초기값을 5 까지 만들었습니다.
	dp[0] = [MAX, MAX];
	dp[1] = [MAX, MAX];
	dp[2] = [1, 1];
	dp[3] = [MAX, MAX];
	dp[4] = [2, 2];
	dp[5] = [MAX, 1];

	for (let i = 6; i < 100001; i++) {
		dp[i] = [];

		// 2 원만 사용하는 경우
		dp[i][0] = i % 2 === 0 ? i / 2 : MAX;

		// 2 원과 5 원을 사용하는 경우
		dp[i][1] = Math.min(dp[i - 5][1] + 1, dp[i][0]);
	}

	return dp[n][1] === MAX ? -1 : dp[n][1];
};

console.log(solution(input));