백준 1149번: RGB거리 - javascript

백준 1149번: RGB거리

문제 설명

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

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

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

입력

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

출력

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

접근

dp문제에 익숙해졌다고 생각했지만… 또 dp문제를 단방향적으로, 그저 이전 최종 결과에 영향받아 다음 결과를 정하는 코드를 또 짜고 말았다. 항상 조건이 여러가지가 나오면 여러가지의 조건에 대한 각각의 dp알고리즘을 짜도록 해야겠다…

function rgb(dp,n){
  let min = dp[0].indexOf(Math.min(...dp[0]));
  let result = dp[0][min];
  for(let i =1;i<n;i++){
    min = dp[i].indexOf(Math.min(dp[i][(min+1)%3], dp[i][(min+2)%3]));
    result += dp[i][min];
  }
  return result;
}

약간 이런식으로 접근했는데,모르는 사람이 보면 정말 더러운 코드다.

대략적인 초기 생각은 i번째에서 최소 비용인 색깔을 고르면 i+1번째에는 해당 색을 제외한 나머지 2가지 색깔 중 최소 비용인 색을 마저 고르겠다는 것이다. 빨강 -> 초록 -> 빨강이여도, 빨강 -> 초록 -> 파랑 이여도 상관없지 않나 해서 나온 생각이였다.

하지만 이번 문제는 그런식으로 풀어나가면 안된다는 것을 한참 뒤 에서야 깨달았다.

1번째 집에서 빨강을 고를 수 도, 파랑을 고를 수 도, 초록을 고를 수 도 있다. 문제는 여기서 최소비용인 색을 골라도 최종이 최소비용일지 모른다는 것이다. 따라서 이 문제는 [10844번: 쉬운 계단 수]처럼 각각의 경우에 대해 0부터 N까지 결과를 가지고 간 다음에 최종적으로 최소비용 비교를 해야 한다.

그리고 색을 고를때에도 현재 색을 기반으로 다음 색을 고르는 것이 아니라 어차피 끝까지 갈 것이므로 i번째의 색의 비용은 i-1번째의 나머지 2가지 색깔 중 최소 비용과 더한 값이 되어야 한다.

그렇게 되면 i번째 빨강은 i-1까지의 초록 혹은 파랑 중 최소 비용과 결합 할 것이고,

i번째 파랑은 i-1까지의 초록 혹은 빨강 중 최소 비용과 결합 할 것이고,

i번째 초록은 i-1까지의 빨강 혹은 파랑 중 최소 비용과 결합 할 것이다.

최종적으로는 N번째에서 각자 서로 최소비용을 고르면서 올라온 빨강, 파랑, 초록의 최종비용이 나오게 된다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let n = input.splice(0,1);
  let dp = [];
  let arr = [];
  //모든 비용이 저장된 dp 배열과 아무것도 안들어간 arr배열 초기화
  input.reduce((acc,cur)=>{
    dp.push(cur.split(' ').map(Number));
    arr.push([0,0,0]);
  },'')
  let answer = rgb(arr, dp, n);
  console.log(answer)
  process.exit();
});

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