[백준 / 17404 / Python] RGB거리 2

문제 요약

N개의 집이 일렬로 있고, 각 집을 빨강, 초록, 파랑 중 하나로 칠해야 합니다.
각 집을 각 색으로 칠하는 비용이 주어질 때,

• 1번 집의 색은 2번, N번 집의 색과 달라야 하고
• N번 집의 색은 N-1번, 1번 집의 색과 달라야 하며
• 나머지 집도 인접한 집과 색이 달라야 합니다.
  이 조건을 모두 만족하면서 모든 집을 칠하는 최소 비용을 구하는 문제입니다.

---

접근 방식

이 문제는 "원형" 형태의 인접 제약이 추가된 RGB거리 문제입니다.
즉, 1번 집과 N번 집도 서로 색이 달라야 하므로,
단순한 DP로는 해결이 어렵고,
1번 집의 색을 고정한 뒤,

• 1번 집을 빨강/초록/파랑 각각으로 칠하는 경우를 모두 시도
• 그에 따라 N번 집이 같은 색이 되지 않도록 DP를 돌려
• 세 경우 중 최소값을 정답으로 선택
  하는 방식으로 해결합니다.

실생활 비유로 설명하면,
"원형 테이블에 앉은 사람들에게 옷 색을 입히는데,
첫 번째와 마지막 사람도 서로 다른 색이어야 하니
첫 사람의 옷 색을 정해놓고,
끝까지 돌려보며 가장 싼 경우를 찾는 것"과 같습니다.

---

코드 구현

아래는 Python으로 구현한 코드입니다.

import sys
input = sys.stdin.readline
INF = sys.maxsize

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

for first_color in range(3):
    dp = [[INF] * 3 for _ in range(N)]
    dp[0][first_color] = costs[0][first_color]

    for i in range(1, N):
        r, g, b = costs[i]
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r  # 빨강
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g  # 초록
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b  # 파랑

    for last_color in range(3):
        if last_color == first_color:
            continue
        else:
            answer = min(answer, dp[N - 1][last_color])

print(answer)

---

시간복잡도 & 최적화

• 시간복잡도:
  • 1번 집의 색을 3가지로 고정해 각각 DP 수행: O(3 × N)
  • 각 집마다 3가지 색에 대해 이전 집의 다른 색만 고려: O(N)
  • 전체적으로 O(N) (N ≤ 1,000)
• 최적화 포인트:
  • 1번 집의 색을 고정해 원형 제약을 선형 문제로 변환
  • DP 테이블을 매번 새로 만들어 불필요한 상태 중복 방지

---

느낀 점 / 팁

• 원형 제약(첫 집과 마지막 집도 인접) 문제는
  "시작 상태를 고정해서 여러 번 DP"로 푸는 패턴을 익혀두면 좋습니다.
• DP 테이블을 매번 새로 만들어
  시작 색에 따라 독립적으로 계산하는 것이 실수 방지에 효과적입니다.
• RGB거리 1(선형)과 2(원형)의 차이를 명확히 이해하면
  다양한 변형 문제에도 쉽게 응용할 수 있습니다.

---

참고

• 백준 17404번 문제 링크
• 동적 프로그래밍(DP) 위키백과
• RGB거리 1 (백준 1149)

---

import sys
input = sys.stdin.readline
INF = sys.maxsize

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

for first_color in range(3):
    dp = [[INF] * 3 for _ in range(N)]
    dp[0][first_color] = costs[0][first_color]

    for i in range(1, N):
        r, g, b = costs[i]
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r  # 빨강
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g  # 초록
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b  # 파랑

    for last_color in range(3):
        if last_color == first_color:
            continue
        else:
            answer = min(answer, dp[N - 1][last_color])

print(answer)