[TIL] 백준 1149 - RGB거리 ( python )

📌 문제 탐색하기

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 합니다.
각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때,
아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보는 것이 핵심입니다.

< 조건 >

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

가능한 시간복잡도

1. 조합
   
   • 모든 가능한 비용의 조합을 다 시도해야 하므로 가능한 조합은 3 * 2^(N-1)개로 매우 비효율적입니다.
2. DP ( 동적계획법 )
   • 연속한 두 집은 같은 색을 칠할 수 없습니다.
   • 따라서, i번째 집을 빨간색으로 칠할 때, 이전 (i-1)번째 집은 초록 또는 파랑이어야 합니다.
     
     • dp[i][빨강] = min(dp[i-1][초록], dp[i-1][파랑]) + cost[i][빨강]
     • dp[i][초록] = min(dp[i-1][빨강], dp[i-1][파랑]) + cost[i][초록]
     • dp[i][파랑] = min(dp[i-1][빨강], dp[i-1][초록]) + cost[i][파랑]
   • 매번 이전 집의 상태(3가지)만을 기억하여 한 번만 계산하면 되기 때문에 시간복잡도가 O(N)입니다.

알고리즘 선택

효율적으로 중복을 방지하고 빠르게 최적의 값을 찾을 수 있는 DP(동적계획법)을 사용하여 접근해 보겠습니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. DP 테이블 초기화:
   1.  크기가 3 * N인 2차원 배열 dp를 생성합니다.
   2. dp[0]에는 cost[0]을 할당합니다.
   3. dp[i][j]: i번째 집을 색상 j로 칠할 때까지의 최소 누적 비용입니다.
3. 점화식 수행:
   • 1부터 N-1까지 DP 점화식을 수행합니다.
   • dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
     dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
     dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]
4. 결과 출력: 마지막 집에서 세 색상 중 최소 비용 출력합니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

N = int(input())
cost = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * 3 for _ in range(N)]
dp[0] = cost[0]

for i in range(1, N):
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]

print(min(dp[N - 1]))