[C4] 1149 - RGB거리

문제

풀이

DP를 이용해 직전 집을 칠하는 데 드는 비용의 최솟값으로부터 현재 집을 칠하는데 필요한 비용을 계산한다.

예를 들어 직전 집을 칠하는데 각각 100, 200, 300원이 들었고, 지금 집을 빨간색으로 칠하는데 50원이 든다면

직전 집들을 칠하는 비용 + 지금 집을 빨간색으로 칠하는데 드는 비용을 비교해서 집을 빨간색으로 칠하는데 드는 최소 비용을 찾아준다.

위 예시에서는 150, 250, 350중 최솟값인 150원이 이 집을 빨간색으로 칠하는데 드는 비용이다.

이 조건만 보면 간단한 dp로 해결 할 수 있다.

 

하지만 주의해야 할 것은 직전 집과 같은 색상으로는 칠할 수 없다는 조건이 붙어있다.

 이전 집을 빨간색으로 칠했다면, 다음 집은 빨간색이 아니라 초록색 또는 파란색으로밖에 칠할 수 없다는 것이다.

그렇기 때문에, dp를 이용해 직전 집을 칠하는 비용들 중, 현재 집을 칠하려는 색상에 사용된 비용을 제외하고 나머지 두 비용끼리 비교해 주면 되는 것이다.

말로는 어려우니 그림으로 보자면

지금 집을 칠하는데 드는 총 비용 = 이전 집들을 현재와 다른 색으로 칠하는데 드는 누적 비용 + 현재 집을 칠하는데 드는 비용의 최솟값

으로 보면 되는 것이다.

 

코드로 한번 살펴보자

//input
//[3]
//[26, 40, 83]
//[49, 60, 57]
//[13, 89, 99]
//input은 모두 split 후 number로 변환한 상태

const [n] = input[0];

//dp 배열을 만들어준다
//dp는 1번부터 시작하도록 맨 첫 배열을 [0,0,0]으로 놔둠(사용하지 않는 배열)
const dp = Array.from({ length: n + 1 }, () => Array(3).fill(0));
for (let i = 0; i < 3; i++) {
	//dp의 1번 비용들(초기값)을 설정
	dp[1][i] = input[1][i];
}

 

dp 배열 생성 후, 각 값을 채워주면 된다

 

//초기값 다음의 집들부터 값 넣어주기
//i번째 집을 탐색
for (let i = 2; i <= n; i++) {
  //각 색상별 누적합 구하기
  //j = 현재 칠하려고 하는 색상 (0:r, 1:g, 2:b)
  for (let j = 0; j < 3; j++) {
    //이전 집에서 칠했던 색상을 뺴고 비교
    //k = 이전 집을 칠했던 색상
    for (let k = 0; k < 3; k++) {
      //현재 칠하려는 색상과 이전 집을 칠한 색상이 같으면 pass
      if (j === k) continue;
      //현재 집을 각 색상별로 칠하려는 비용의 최솟값을 구함
      dp[i][j] =
        dp[i][j] === 0
          ? dp[i - 1][k] + input[i][j]
          : Math.min(dp[i - 1][k] + input[i][j], dp[i][j]);
    }
  }
}

 

모든 과정을 거치면 dp의 마지막 요소는 각 색상별 누적합이 나올텐데, 이중 최솟값을 구해 출력해주면 된다.

 

코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line.split(" ").map(Number));
}).on("close", () => {
  const [n] = input[0];

  const dp = Array.from({ length: n + 1 }, () => Array(3).fill(0));

  for (let i = 0; i < 3; i++) {
    dp[1][i] = input[1][i];
  }

  for (let i = 2; i <= n; i++) {
    for (let j = 0; j < 3; j++) {
      for (let k = 0; k < 3; k++) {
        if (j === k) continue;
        dp[i][j] =
          dp[i][j] === 0
            ? dp[i - 1][k] + input[i][j]
            : Math.min(dp[i - 1][k] + input[i][j], dp[i][j]);
      }
    }
  }

  console.log(Math.min(...dp[n]));
  process.exit(0);
});