[알고리즘] 백준 - 1149 RGB 거리 node js 구현

설명

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

 

해설

 아래와 같이 집1, 집2, 집3인 경우의 R,G,B 페인트를 칠하는 비용이 있다고 가정한다.

Dynamic programming은 이전 계산값을 저장해서 다음 계산에 사용한다고 생각할 수 있다.

아래 그림을 보면 위에서 만든 자료구조를 가지고 같은 모양(열과 행이 같은) 자료구조를 만들어 자료를 업데이트 하는 것을 볼 수 있다.

업데이트를 하는 과정은 아래와 같다.

1. 각 샐은 현재 집을 해당 컬럼(R,G,B)로 칠했을때의 최소 비용이다.

2. 집2에 빨간색을 칠하는 경우 : 집2를 빨간색으로 칠하는 비용 + 최소값(집1을 초록색으로 칠하는 경우, 집 1을 파란색으로 칠하는 경우)

    집2에 파란색을 칠하는 경우 : 집2를 파란색으로 칠하는 비용 + 최소값(집1을 초록색으로 칠하는 경우, 집 1을 빨간색으로 칠하는 경우)

위 2개의 규칙을 따라서 전체 셀을 업데이트 한다.

마지막까지의 최소비용을 구하면 해당 row에서 가장 최소인 값을 출력해주면된다.

 

코드

 

 

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
 
// 입력값을 2중 배열로 저장해놓는다.
var numberOfHouses = parseInt(input[0]);
const costsForPainting = []
for(let i = 1; i <= numberOfHouses; i++) {
  costsForPainting.push(input[i].split(" ").map(el => parseInt(el)))
}
 
// 최솟값을 이용하여 계산하는 부분이 많이 때문에 최솟값을 구하는 함수를 미리 짜둔다
function min(list) {
  let min
  for(const num of list) {
    if(!min) {
      min = num
      continue
    }
    if(num < min) min = num
  }
  return min
}
 
// 그림에서 설명한것과 같이 2중 list를 만들어야 한다.
const minCostForPainting = []
for(let i = 0; i < numberOfHouses; i++) {
  // 첫번째 집에 경우 기존 입력값을 그대로 사용한다.
  if(i === 0) {
    minCostForPainting.push(costsForPainting[0])
    continue
  }
 
  // 현재 집(i)를 생상별로 칠할때의 최소 비용을 구한다.
  // 현재 집을 Red로 칠하는 경우 = 현재집을 red로 칠하는 비용 + 이전집을 green blue로 칠할때 비용 중 최소값.
  const currentHouseRedCost = costsForPainting[i][0] + min([minCostForPainting[i-1][1], minCostForPainting[i-1][2]])
  const currentHouseGreenCost = costsForPainting[i][1] + min([minCostForPainting[i-1][0], minCostForPainting[i-1][2]])
  const currentHouseBlueCost = costsForPainting[i][2] + min([minCostForPainting[i-1][0], minCostForPainting[i-1][1]])
 
  const currentMinCost = [currentHouseRedCost, currentHouseGreenCost, currentHouseBlueCost]
  minCostForPainting.push(currentMinCost)
}
console.log(min(minCostForPainting[minCostForPainting.length - 1]))