[백준17404_자바스크립트(javascript)] - RGB 거리2

🔴 문제

RGB 거리2

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

let ans = Infinity;
for (let startColor = 0; startColor < 3; startColor++) {
  const dp = Array.from({ length: n }, () => Array(3).fill(Infinity));
  dp[0][startColor] = inputs[0][startColor];

  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + inputs[i][0];
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + inputs[i][1];
    dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + inputs[i][2];
  }

  for (let endColor = 0; endColor < 3; endColor++) {
    if (startColor === endColor) continue;
    ans = Math.min(ans, dp[n - 1][endColor]);
  }
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

RGB 거리1랑 같은 문제인데 맨 마지막집과 첫번째 집이 같은 색으로 칠해지면 안된다는 조건이 추가된 문제다.

이 경우에는 총 세 개의 집을 기준으로 dp를 세번 수행해주면 된다.
첫번째 집이 빨간색일 경우를 기준으로 DP를 수행하고, 마지막 집이 빨간색이 아닌경우로 정답을 갱신해주면 된다.
이 경우를 각 색별로 체크해줘서 총 6가지 경우의 수를 다 계산해준다고 보면된다.

흑흑 이 문제는 두번째 푸는건데도 못풀었다.
괜찮음 한번 더 풀어보면됨 ㅋㅋ ㅠ
dp는 진짜 너무너무 어렵다~~~

🔵 Ref