설탕 배달

문제

언어

  • JavaScript

문제 풀이 step 1

  • 착안
    • 마지막 단계에 봉지를 추가할 때, 3kg짜리 봉지를 추가하거나 5kg짜리 봉지를 추가합니다.
  • 점화식
    • dp[N] = Nkg을 담을 때 사용하는 최소 봉지의 개수
  • 경우
    1. 정확히 Nkg를 만들 수 없는 경우
    2. 정확히 Nkg을 만들 수 있지만 3kg 혹은 5kg 중 한 종류만 사용가능한 경우
    3. 정확히 Nkg을 만들 수 있고, 두 종류 다 사용가능한 경우

소스 코드

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

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

	const dp = new Array(N + 1);
	dp[0] = dp[1] = dp[2] = dp[4] = -1;
	dp[3] = dp[5] = 1;

	for (let i = 6; i < N + 1; i++) {
		if (dp[i - 3] === -1 && dp[i - 5] === -1) dp[i] = -1;
		else {
			if (dp[i - 3] * dp[i - 5] < 0) dp[i] = Math.max(dp[i - 3], dp[i - 5]) + 1;
			else dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;
		}
	}

	console.log(dp[N]);
};

solution(input);