[boj] 17404. RGB거리 2 (node.js)

문제

[boj] 17404. RGB거리 2 (node.js)

핵심 풀이

• 1번과 N번 집을 제외한 2 ~ N-1 번째 집은 모두 양 옆의 집과 색이 달라야 한다.
• 따라서 1번 집부터 색칠한다고 할 때, 다음 집의 색을 칠할 때 이전 집을 고려한다. 이렇게 하면 이전 집 기준으로 다음 집의 색이 다르다는 것은 보장된다.
• 마지막 집을 칠할 때, 첫 번째 집과 색이 달라야 한다. 이를 보장하기 위해 첫 번째 집의 색상을 3가지 중 하나로 반복문을 돌며 고정시키고, 각 경우에 따른 최솟값을 구했다.

let result = 1000 * N; // 최솟값을 구해야 하므로 최댓값으로 초기화
for (let selected = 0; selected < 3; selected++) {
  dp[0] = new Array(3).fill(arr[0][selected]); // 첫 번째 집의 색상 고정
  for (let i = 1; i < N; i++) {
    dp[i] = []; // 새로운 색상마다 배열 초기화
    for (let j = 0; j < 3; j++) {
      dp[i][j] = 1000 * (i + 1); // i번째 집 (0부터이므로 + 1) 까지의 최댓값(누적)으로 초기화
      for (let prev = 0; prev < 3; prev++) {
        if (i == 1) {
          // 두 번째 집이라면 첫 번째 집에 고정해둔 색상과 반드시 달라야만 함
          if (j == selected) continue;
        } else {
          // 두 번째 집이 아니라면 이전 집의 색상과 달라야 함
          if (j == prev) continue;
        }
        if (i == N - 1 && selected == j) continue; // 마지막 집이라면 고정 색상과 달라야 함
        dp[i][j] = Math.min(dp[i - 1][prev] + arr[i][j], dp[i][j]); // 갱신
      }
    }
  }
  result = Math.min(...dp[N - 1], result);
}

생각

• 틀렸던 이유:dp[i][j] = 1000 * (i + 1);
  • dp[i][j]를 초기화할 때, 항상 최솟값이 갱신될 수 있도록 최댓값을 초기값으로 대입해야 한다. 이 문제의 경우, dp 배열의 값은 항상 n-1번째 집과 합산되어 '누적' 됨을 유의해야 한다. 예를 들어 5번째 집의 색상 비용은 최대 1000이지만, dp배열에 저장되는 누적 최솟값은 최대 1000 * 5 일 수 있다. 따라서 이 경우 초기값은 1000 * 5 여야 한다.

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = +input();
  const arr = [];
  const dp = [];
  for (let i = 0; i < N; i++) arr[i] = input().split(" ").map(Number);

  let result = 1000 * N;
  for (let selected = 0; selected < 3; selected++) {
    dp[0] = new Array(3).fill(arr[0][selected]);
    for (let i = 1; i < N; i++) {
      dp[i] = [];
      for (let j = 0; j < 3; j++) {
        dp[i][j] = 1000 * (i + 1);
        for (let prev = 0; prev < 3; prev++) {
          if (i == 1) {
            if (j == selected) continue;
          } else {
            if (j == prev) continue;
          }
          if (i == N - 1 && selected == j) continue;
          dp[i][j] = Math.min(dp[i - 1][prev] + arr[i][j], dp[i][j]);
        }
      }
    }
    result = Math.min(...dp[N - 1], result);
  }
  console.log(result);
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});