백준1149 - RGB거리 (DP) JS

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

문제를 간단히하면 옆에 있는 집과 색이 같지 않게끔 하면서 색을 칠했을 때의 최소비용을 구하는 문제다.

이 문제는 다이나믹 프로그래밍을 통해 해결할 수 있는데, 아래 표로 이해를 도우려한다.

먼저 위의 예제를 빌려, 1번째 집이 각각의 색으로 색칠할 때의 비용과 2번째 집을 붉은 색으로 칠할 때의 비용만 주어진다고 가정하자.

	Red	Green	Blue
1	26	40	83
2	49 (채택)	-	-

 

이때의 2번집을 붉은 색으로 칠할 때의 최소비용은 89이 된다.

(옆집과 같은 색은 사용할 수 없고, 남은 녹색과 푸른색 중 더 값싼 녹색을 선택해야 하기 때문.)

	Red	Green	Blue
1	- (동일한 색 선택 불가)	40 (최솟값)	83
2	89 (49 + 40)	-	-

 

이를 응용하면 각 색별로 칠했을 때의 최소비용을 알 수 있게 된다.

	Red	Green	Blue
1	26	40	83
2	49	60	57
3	13	89	99

 

문제에서 제시된 예제로 설명하면, 아래와 같이 최소비용이 도출 가능하다. (붉은색 - 푸른색 - 붉은색을 선택하는 경우 최솟값임)

	Red	Green	Blue
1	26	40	83
2	89 (49 + 40)	86 (60 + 26)	83 (57 + 26)
3	96 (13 + 83)	172 (89 + 83)	185 (99 + 86)

 

이 논리를 코드로 옮기면 다음과 같이 작성할 수 있다.

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

const N = input.shift()
function solution(data) {
  const arr = data.map((el)=> el.split(" ").map(Number))
  for(let i = 1 ; i < N ; i ++) {
    arr[i][0] = arr[i][0] + Math.min(arr[i-1][1], arr[i-1][2])
    arr[i][1] = arr[i][1] + Math.min(arr[i-1][0], arr[i-1][2])
    arr[i][2] = arr[i][2] + Math.min(arr[i-1][0], arr[i-1][1])
  }
  console.log(Math.min(...arr.at(-1)))
}
solution(input)