RGB거리

문제

• 백준 1149번 - RGB거리

언어

• JavaScript

문제 풀이 step 1

• dp[n][0] = n 번째 집을 Red로 칠한 경우
• dp[n][1] = n 번째 집을 Green으로 칠한 경우
• dp[n][2] = n 번째 집을 Blue로 칠한 경우
• DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
• 앞의 n - 1 만큼의 과정은 완성되어 있다고 가정하고, n번째를 생각해보겠습니다.
• 경우의 수는 3가지가 나옵니다. 마지막 집을 Red로, Green으로, Blue로 칠한 경우
  • 마지막 집을 Red로 칠한 경우는 그 앞 집이 Green이거나 Blue인 경우만 올 수 있습니다.
    • dp[n][0] = Math.min(dp[n - 1][1], dp[n - 1][2]) + Red
  • 마지막 집을 Green로 칠한 경우는 그 앞 집이 Red이거나 Blue인 경우만 올 수 있습니다.
    • dp[n][1] = Math.min(dp[n - 1][0], dp[n - 1][2]) + Green
  • 마지막 집을 Blue로 칠한 경우는 그 앞 집이 Red이거나 Green인 경우만 올 수 있습니다.
    • dp[n][2] = Math.min(dp[n - 1][0], dp[n - 1][1]) + Blue

소스 코드

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

const solution = (input) => {
	let N = parseInt(input[0]);
	const dp = Array.from({length: N}, () => []);

	// base
	dp[0] = input[1].split(" ").map(Number);
	for (let i = 1; i < N; i++) {
		const [R, G, B] = input[i + 1].split(" ").map(Number);

		dp[i][0] = R + Math.min(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = G + Math.min(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = B + Math.min(dp[i - 1][0], dp[i - 1][1]);
	}

	return Math.min(...dp[N - 1]);
};

console.log(solution(input));