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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
예제 입력 1
3 26 40 83 49 60 57 13 89 99예제 출력 1
96출처
- 문제를 번역한 사람: baekjoon
- 빠진 조건을 찾은 사람: djm03178
- 문제의 오타를 찾은 사람: fail456
- 데이터를 추가한 사람: rdd6584
해결한 코드
function b1149() {
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
var n = parseInt(input[0])
var answer = Array(n)
var paint = []
for (var i = 1; i < input.length; i++) {
var c = input[i].split(' ').map(e => e = e / 1)
paint.push(c)
}
var d = Array(paint.length).fill(0)
for(var i=0; i<d.length; i++){
d[i] = [0, 1, 2]
}
d[0][0] = paint[0][0]
d[0][1] = paint[0][1]
d[0][2] = paint[0][2]
for(var j=1; j<n; j++){
d[j][0] = Math.min(d[j-1][1], d[j-1][2]) + paint[j][0]
d[j][1] = Math.min(d[j-1][0], d[j-1][2]) + paint[j][1]
d[j][2] = Math.min(d[j-1][0], d[j-1][1]) + paint[j][2]
}
console.log(Math.min.apply(null, d[n-1]))
}
b1149()알고리즘
※ 다이나믹 프로그래밍으로 푼다
1. 초기값을 정한다.
첫번째 집이 선택할 수 있는 페인트 색은? 빨강, 파랑, 초록
Price_for_first = [red, blue, green] // 첫번째 집이 페인트 칠할 때의 색깔별 가격 d[1] = [red, blue, green] // 첫번째 집은 빨강으로 칠할때 red, 파랑일떄 blue, 초록일떄 green을 지불한다.2. 점화식을 세운다.
두번째 집이 선택할 수 있는 페인트 색은?
- 만약 빨강을 선택한다면? 첫번째 집은 파랑 or 초록을 선택했어야 한다.
2번째 집이 빨강 + 첫번째 집이 파랑 vs 2번째 집이 빨강 + 첫번째 집이 초록
둘 중 작은 값이 두번째 집을 빨강으로 칠했을 때 첫번째 ~ 두번째 집까지 페인트칠 하는 최소 비용이 된다.- 만약 파랑을 선택? 첫번째 집은 빨강 or 초록 선택
2번째 집이 파랑 + 첫번쨰 집이 빨강 vs 2번째 집이 파랑 + 첫번째 집이 초록
둘 중 작은 값이 두번째 집을 파랑으로 칠했을 때 첫번째 ~ 두번째 집까지 페인트칠하는 최소 비용이 된다.- 만약 초록을 선택? 첫번째 집은 빨강 or 파랑 선택
2번째 집이 초록 + 첫번쨰 집이 빨강 vs 2번째 집이 초록 + 첫번째 집이 파랑
둘 중 작은 값이 두번째 집을 초록으로 칠했을 때 첫번째 ~ 두번째 집까지 페인트칠하는 최소 비용이 된다.이를 식으로 표현하면
Price_for_second = [red_second, blue_second, green_second] // 두번째 집 가격 redMin = min(d[1][blue], d[1][green]) + red_second blueMin = min(d[1][red], d[1][green]) + blue_second greenMin = min(d[1][red], d[1][blue]) + green_second d[2] = [redMin, blueMin, greenMin]이렇게 되므로, 점화식으로 나타내면
paint = [ [26, 40, 83], // 첫번째 집 페인트 칠할 때 가격 [49, 60, 57], // 두번째 집 페인트 칠할 때 가격 [13, 89, 99] // 세번째 집 페인트 칠할 때 가격 ] // 만약 첫번째 집을 인덱스 0으로 두면 d[0][0] = paint[0][0] // 빨강 d[0][1] = paint[0][1] // 파랑 d[0][2] = paint[0][2] // 초록 // 두번째 집부터 // 집 순서를 n으로 두면 d[n-1][0] = min(d[n-2][1], d[n-2][2]) + paint[n-1][0] // 현재 집 빨강 칠할 때, 이전 집은 파랑 아님 초록 중 합이 더 저렴한 것 d[n-1][1] = min(d[n-2][0], d[n-2][2]) + paint[n-1][1] // 파랑으로 칠할 때, 이전 집이 빨강 아님 초록 중 합이 더 저렴한 것 d[n-1][2] = min(d[n-2][0], d[n-2][1]) + paint[n-1][2] // 초록으로 칠할 떄, 이전 집이 빨강 아님 파랑 중 합이 더 저렴한 것이렇게 되면, 다음 집에 대한 페인트칠 비용을 계산하면서 이전 집들의 비용까지 누적되어 계산된다.
3. 마지막 집에 대한 d 배열의 원소 중 최솟값을 출력한다.
집의 갯수는 n개니까
d[n]의 원소 중 최솟값을 가져오면 된다.
(참고로 나는 인덱스가 집 순서보다 1 작으므로,d[n-1]을 가져왔다.)
현재 집에 대하여 최소 비용 값을 계산할 때 색깔별로 칠했을 때의 누적된 최소 비용에 따라 계산했어야 했는데, 처음엔 그때그때에 맞는 최솟값을 찾아 계산해서 틀렸었다..
언제나 열심히해도 부족한 알고리즘 공부..
오늘 코테를 봤는데, 확실하게 절감했다. 🤦🏻♀️
개발 공부하는 심리학도