2021. 7. 2. 13:23ㆍFront-end/알고리즘
문제를 풀기 위한 아이디어
규칙이 복잡해보이지만 숫자를 대입하여 생각해보면 결국 바로 인접한 집끼리만 다른 색이면 된다는 것이다.
일단 주어진 각 집을 빨강,초록,빨강으로 칠하는 비용들을 2차원 배열에 저장한다.
input = [
[26, 40, 83],
[49, 60, 57],
[13, 89, 99]
]
그 다음으로는 첫번째집을 R로 칠한 경우 / 첫번째 집을 G로 칠한 경우 / 첫번째 집을 B로 칠한 경우를 모두 다 따져주면 된다.
이를 점화식으로 세우면, 두번째 집부터는 다음과 같은 점화식이 성립한다.
input[i][0] = min(input[i-1][1], input[i-1][2]) + input[i][0]
input[i][1] = min(input[i-1][0], input[i-1][2]) + input[i][1]
input[i][2] = min(input[i-1][0], input[i-1][1]) + input[i][2]
즉 현재 집이 R로 칠했다는 것은 바로 직전의 집이 G, B 중에 최솟값이었다는 것이다.
현재 집이 G로 칠했다는 것은 바로 직전의 집이 R, B 중 최솟값이었다는 것이 된다.
마찬가지로 현재 집이 B로 칠했다는 것은 바로 직전의 집이 R, G 중 최솟값이었다는 것이 된다.
그리고 해당 칸에 자기 자신을 더한 것을 누적한다.
그렇게 끝까지 구하면 맨 마지막 집의 R, G, B 중 최솟값을 출력하면 그것이 모든 집을 최소 비용으로 규칙에 맞게 칠한 것이 된다.
매우 간단한 코드로 작성할 수 있다. 시간 복잡도가 O(N)으로 한번만 돌면서 모든 것을 처리할 수 있다.
내가 작성한 코드 (자바스크립트)
let fs = require("fs");
let input = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(input[0]);
input.shift();
input = input.map((value) =>
value.split(" ").map((element) => Number(element))
);
for (let i = 1; i < N; i++) {
input[i][0] = Math.min(input[i - 1][1], input[i - 1][2]) + input[i][0];
input[i][1] = Math.min(input[i - 1][0], input[i - 1][2]) + input[i][1];
input[i][2] = Math.min(input[i - 1][0], input[i - 1][1]) + input[i][2];
}
console.log(Math.min(...input[N - 1]));
'Front-end > 알고리즘' 카테고리의 다른 글
[백준] 1655. 가운데를 말해요 (자바스크립트/javascript/node.js/힙정렬/우선순위 큐) (0) | 2021.07.02 |
---|---|
[프로그래머스] N으로 표현 (자바스크립트/javascript/js/동적계획법/동적프로그래밍/다이나믹프로그래밍) (0) | 2021.07.02 |
[백준] 9461. 파도반 수열 (자바스크립트/javascript/js/node.js/동적계획법/다이나믹 프로그래밍/동적 프로그래밍) (0) | 2021.07.01 |
[알고리즘] 동적계획법 (동적프로그래밍, 다이나믹 프로그래밍) (자바스크립트/javascript/js) (0) | 2021.07.01 |
[백준] 1904. 01타일 (자바스크립트/javascript/js/동적계획법/다이나믹프로그래밍/동적프로그래밍) (0) | 2021.07.01 |