[BOJ] 1149. RGB거리

📌 문제 제목

문제 링크: BOJ 1149

---

🗒️ 문제 설명

RGB거리에는 N개의 집이 1번부터 순서대로 있다.

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

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

시간 제한: 0.5초

메모리 제한: 128MB

2 <= N <= 1,000

집을 칠하는 비용 <= 1,000

---

💡 문제 해결 아이디어

• 테이블 정의
  • dp[i]는 i번째 집까지 칠할 때의 최소 비용
  • dp[i][0]은 i번째 집이 빨강
  • dp[i][1]은 i번째 집이 초록
  • dp[i][2]는 i번째 집이 파랑
• 점화식 찾기
  • dp[1]
    • dp[1][0] = costs[0][0]
    • dp[1][1] = costs[0][1]
    • dp[1][2] = costs[0][2]
  • dp[2]
    • dp[2][0] = min(dp[1][1], dp[1][2]) + costs[1][0]
    • dp[2][1] = min(dp[1][0], dp[1][2]) + costs[1][1]
    • dp[2][2] = min(dp[1][0], dp[1][1]) + costs[1][2]
  • 점화식
    • dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0]
    • dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1]
    • dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2]
• 초기값 정하기
  • dp[1][0] = costs[0][0]
  • dp[1][1] = costs[0][1]
  • dp[1][2] = costs[0][2]

---

⌛️ 시간 복잡도

• O(3N) -> O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

N = int(input().strip())
costs = [list(map(int, input().split())) for _ in range(N)]  # RGB 비용

dp = [[-1] * 3 for _ in range(N+1)]
dp[1][0] = costs[0][0]
dp[1][1] = costs[0][1]
dp[1][2] = costs[0][2]

for i in range(2, N+1):
    for j in range(3):
        if j == 0:
            dp[i][j] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][j]
        elif j == 1:
            dp[i][j] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][j]
        elif j == 2:
            dp[i][j] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][j]

print(min(dp[N]))