[백준] 1149. RGB거리 풀이 / Python, JavaScript

1149번: RGB거리

 

1149. RGB거리

무작정 1행부터 이전 색깔을 제외하고 가장 작은 값들만 찾아 더해가면 일부 케이스에서 틀리게 됩니다. 각 행마다 나올 수 있는 비용은 총 3가지 이기 때문에 매번 3가지 경우의 비용을 모두 계산해주어야 합니다.

 

매 행에 들어있는 값을 빨강(R), 초록(G), 파랑(B)이라고 할 때 각 열의 누적 비용은 다음과 같습니다.

현재 행의 R의 누적 비용 = 현재 행의 R의 비용 + 이전 행의 B의 누적 비용과 G의 누적 비용중 더 작은 값

현재 행의 G의 누적 비용 = 현재 행의 G의 비용 + 이전 행의 R의 누적 비용과 B의 누적 비용중 더 작은 값

현재 행의 B의 누적 비용 = 현재 행의 B의 비용 + 이전 행의 R의 누적 비용과 G의 누적 비용중 더 작은 값

 

이 과정을 마지막 행까지 반복하면 마지막 행에 경우의 수 세가지의 누적 비용이 담기게 되고 이들 중 최솟값이 모든 집을 칠하는 비용의 최솟값이 됩니다.

 

예제1을 예시로 봅시다.

1행: 26 40 83
2행: 49 60 57
3행: 13 89 99

1행은 이전 행이 없으므로 넘어갑니다.

2행에서,

R은 49에 40과 83중 더 작은 값인 40을 더한 89가 누적 비용이 됩니다.

G는 60에 26과 83중 더 작은 값인 26을 더한 86이 누적 비용이 됩니다.

B는 57에 26과 40중 더 작은 값인 26을 더한 83이 누적 비용이 됩니다.

마지막 3행에서,

R은 13에 86과 83중 더 작은 값인 83을 더한 96이 누적 비용이 됩니다.

G는 89에 89와 83중 더 작은 값인 83을 더한 172가 누적 비용이 됩니다.

B는 99에 89와 86중 더 작은 값인 86을 더한 185가 누적 비용이 됩니다.

 

마지막 행에서 최솟값 96이 모든 집을 칠하는 비용의 최솟값입니다.

 

점화식은 아래와 같습니다.

테이블[i][R] = array[i][R] + min(테이블[i][G], 테이블[i][B])
테이블[i][G] = array[i][G] + min(테이블[i][R], 테이블[i][B])
테이블[i][B] = array[i][B] + min(테이블[i][R], 테이블[i][G])

 

 

작성 코드 (Python)

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
table = [arr[0]] + [[0] * 3 for _ in range(n - 1)]

for i in range(1, n):
    table[i][0] = arr[i][0] + min(table[i - 1][1], table[i - 1][2])
    table[i][1] = arr[i][1] + min(table[i - 1][0], table[i - 1][2])
    table[i][2] = arr[i][2] + min(table[i - 1][0], table[i - 1][1])
print(min(table[-1]))

작성 코드 (JavaScript)

function solution(n, array) {
  const table = Array.from({ length: n }, () => Array(3).fill(0));
  table[0] = [...array[0]];
  for (let i = 1; i < n; i += 1) {
    table[i][0] = array[i][0] + Math.min(table[i - 1][1], table[i - 1][2]);
    table[i][1] = array[i][1] + Math.min(table[i - 1][0], table[i - 1][2]);
    table[i][2] = array[i][2] + Math.min(table[i - 1][0], table[i - 1][1]);
  }
  return Math.min(...table[n - 1]);
}
solution(3, [[1, 100, 100], [100, 100, 100], [1, 100, 100]]);