[백준/JavaScript] RGB거리 2(17404)

문제

https://www.acmicpc.net/problem/17404

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

 

[ 입력 ]

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

[ 출력 ]

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

풀이

• 첫번째 집과 마지막 집도 색깔이 달라야 한다는 점을 주의하면 된다.
• 첫번째 집의 색깔을 고정해서 3가지 색의 경우를 구하고, 마지막 집의 색상과 비교해서 최소값을 구해낼 수 있다

// 백준 - RGB거리 2(17404)
const solution = ( input ) => {
  const N = parseInt(input.shift());

  let house = [];
  for(let i = 0; i < N; i++) {
    house.push(input.shift().split(" ").map(el => parseInt(el)));
  }

  let answer = Infinity;
  
  for(let first = 0; first < 3; first++) {
    let dp = [];

    let one = first == 0 ? house[0][0] : Infinity;
    let two = first == 1 ? house[0][1] : Infinity;
    let three = first == 2 ? house[0][2] : Infinity;

    // 첫번째 집
    let firstList = [one, two, three];

    dp.push(firstList);

    for(let i = 1; i < N; i++) {
      let line = [];
      // 이전 집과 같은 경우를 제외
      line.push(Math.min(dp[i-1][1], dp[i-1][2]) + house[i][0]);
      line.push(Math.min(dp[i-1][0], dp[i-1][2]) + house[i][1]);
      line.push(Math.min(dp[i-1][0], dp[i-1][1]) + house[i][2]);

      dp.push(line);
    }

    for(let i = 0; i < 3; i++) {
      if(first != i) answer = Math.min(dp[N - 1][i], answer);
    }
  }

  console.log(answer);
}
/*
테스트용: __dirname + '/input.txt'
제출용: '/dev/stdin'
*/
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

solution(input);