[백준 node.js] 1149번_RGB거리

🚩 1463번_1로 만들기 실버3

 

📖 문제 설명 : N 개의 줄에 각각 빨강, 초록, 파랑 집이 주어진다. 

N 번째 선택한 집의 색은 N-1 번째 선택한 집의 색과 같지 않아야 한다.

즉 N 번째 집이 빨간색일 때,  N-1, N+1은 빨간색으로 칠할 수 없다.

또한, 각각의 집의 비용이 다르기 때문에 최소한의 비용을 선택하면서 규칙에 어긋나지 않게

선택해야 한다.

 

💡 모든 경우를 선택해서 마지막에 최솟값을 출력하면 된다. 즉, N 번째 파란색을 선택하는 경우는

N 번째 파란색 집 + N-1 번째 빨간색 집 + N-1 번째 초록색 집의 가격이다.

이 개념을 생각해서 각각의 집을 선택할 때 적용하면 된다.

 

const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n')
const [n, ...n_arr] = input.slice()
const m = n_arr.map((el) => el.trim().split(/\s/).map(Number))

function solution() {
  let answer = 0
  const dp = Array.from(Array(Number(n)), () => Array(3).fill(0))
  // 0번째 초기화
  dp[0][0] = m[0][0]
  dp[0][1] = m[0][1]
  dp[0][2] = m[0][2]
  for (let i = 1; i < Number(n); i++) {
    // i, i-1이 서로 다른 색상을 가져야하기 때문에
    // i에서 가져야 하는 색상을 제외한 색상 중 i-1에서 최소값을 구한다.
    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + m[i][0]
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + m[i][1]
    dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + m[i][2]
  }
  answer = Math.min(...dp[Number(n - 1)]) // 누적된 값중에서 최소값을 찾는다.
  return answer
}

console.log(solution())

👨‍💻 코드 설명

N, N-1이 서로 다른 색상을 가져야 하기 때문에 N에서 가져야 하는 색상을 제외한 색상 중 N-1에서 최솟값을 구한다. dp는 누적된 집의 비용, m은 기존 집의 비용일 때, 점화식으로 표현하면 다음과 같다.

 dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + m[i][0]
 dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + m[i][1]
 dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + m[i][2]

이후 누적된 마지막 집의 빨강, 초록, 파랑 집에서 최소 비용을 return 해주면 된다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.