BaekJoon_1149(RGB 거리)

문제

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

1149번: RGB거리

문제 풀이

문제 조건이 3가지나 있어 복잡 해 보이지만, 결국에는 인접한 집의 경우에는 무조건 다른 색으로 칠해야 한다는 것 이다.

전에 집이 빨간색이면, 다음 집은 초록/파랑

전에 집이 초록색이면, 다음 집은 빨강/파랑

전에 집이 파란색이면, 다음 집은 빨강/초록 이다.

 

2가지 색깔 중 적은 비용을 선택하여 설치하면 된다.

 

첫번째 집을 빨,초,파 로 선택하였을 때를 가정하여 2번째 집 부터 점화식을 세우면 다음과 같다.

dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + dp[i][0]

dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + dp[i][1]

dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + dp[i][2]

 

 

코드

const answer = ([n, ...arr]) => {

    const dp =
        arr.map(list =>
            list.split(' ').map(data => Number(data))
        )

    for (let i = 1; i < n; i++) {
        // 이번에 칠하는게 빨간색이면 그 전에는 초록 or 파란색 중 하나
        dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + dp[i][0];

        // 이번에 칠하는게 초록색이면 그 전에는 빨강 or 파란색 중 하나
        dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + dp[i][1];

        // 이번에 칠하는게 파란색이면 그 전에는 빨강 or 초록색 중 하나
        dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + dp[i][2];
    }

    console.log(Math.min(...dp[n - 1]));
}


const input = [];
require("readline")
    .createInterface(process.stdin, process.stdout)
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        answer(input);
        process.exit();
    });

코드는 깃헙에서도 확인이 가능 합니다 :)

https://github.com/duduchi/Algorithm/tree/main/Dynamic

GitHub - duduchi/Algorithm: 알고리즘 이론 및 구현 소스 정리 프로젝트 입니다.