[백준] 1149 RGB거리

문제를 풀기 위한 아이디어

규칙이 복잡해보이지만 숫자를 대입하여 생각해보면 결국 바로 인접한 집끼리만 다른 색이면 된다는 것이다.

일단 주어진 각 집을 빨강,초록,빨강으로 칠하는 비용들을 2차원 배열에 저장한다.

input = [

[26, 40, 83],

[49, 60, 57],

[13, 89, 99]

]

그 다음으로는 첫번째집을 R로 칠한 경우 / 첫번째 집을 G로 칠한 경우 / 첫번째 집을 B로 칠한 경우를 모두 다 따져주면 된다.

이를 점화식으로 세우면, 두번째 집부터는 다음과 같은 점화식이 성립한다.

input[i][0] = min(input[i-1][1], input[i-1][2]) + input[i][0]

input[i][1] = min(input[i-1][0], input[i-1][2]) + input[i][1]

input[i][2] = min(input[i-1][0], input[i-1][1]) + input[i][2]

 

즉 현재 집이 R로 칠했다는 것은 바로 직전의 집이 G, B 중에 최솟값이었다는 것이다. 

현재 집이 G로 칠했다는 것은 바로 직전의 집이 R, B 중 최솟값이었다는 것이 된다.

마찬가지로 현재 집이 B로 칠했다는 것은 바로 직전의 집이 R, G 중 최솟값이었다는 것이 된다.

그리고 해당 칸에 자기 자신을 더한 것을 누적한다.

그렇게 끝까지 구하면 맨 마지막 집의 R, G, B 중 최솟값을 출력하면 그것이 모든 집을 최소 비용으로 규칙에 맞게 칠한 것이 된다.

매우 간단한 코드로 작성할 수 있다. 시간 복잡도가 O(N)으로 한번만 돌면서 모든 것을 처리할 수 있다.

 

let fs = require("fs");
let input = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(input[0]);
input.shift();
input = input.map((value) =>
  value.split(" ").map((element) => Number(element))
);
for (let i = 1; i < N; i++) {
  input[i][0] = Math.min(input[i - 1][1], input[i - 1][2]) + input[i][0];
  input[i][1] = Math.min(input[i - 1][0], input[i - 1][2]) + input[i][1];
  input[i][2] = Math.min(input[i - 1][0], input[i - 1][1]) + input[i][2];
}
console.log(Math.min(...input[N - 1]));

 

출처: https://nyang-in.tistory.com/266

[백준] 1149. RGB거리 (자바스크립트/javascript/js/node.js/동적 프로그래밍/다이나믹 프로그래밍 / 동적

 

점화식: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ao9364&logNo=221651296608