설명
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에서 가장 최소인 값을 출력해주면된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
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]))
|
cs |
'끄적 > Algorithm' 카테고리의 다른 글
| [알고리즘] 백준 - 3053 택시 기하학 해설, node js 구현 (0) | 2021.08.28 |
|---|---|
| [알고리즘] 백준 - 4153 직각삼각형 node js 구현 (0) | 2021.08.27 |
| [알고리즘] 백준 - 3009 네 번째 점 node js 구현 (0) | 2021.08.22 |
| [알고리즘] 백준 - 1003 피보나치 함수 node js 구현 (0) | 2021.08.20 |
| [알고리즘] 백준 -1085 직사각형에서 탈출 node.js 구현 (0) | 2021.08.17 |
