[백준] 17404 : RGB거리 2

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

---

• 마지막 조건을 먼저 살펴보면, i 번째 집은 앞뒤의 집들과 색깔이 달라야 한다는 것이다.
• 이 조건만 잘 지킨다면, 첫번째 조건에서 2번째 집이 1번째 집과 달라야 한다는 것과 두번째 조건에서 N-1 번째 집이 N 번째 집과 달라야 한다는 조건은 자동으로 지켜진다.
• 결국 따지고 보면 1번 과 N번 집이 달라야 한다는 조건만 추가적으로 지키면 되는데, 총 rgb 3가지 경우 중 두 집이 다른 색깔을 갖는 경우는, 1번 집과 N번 집의 순서가 중요하기 때문에 순열로써 3개 중 2개를 뽑아 6가지가 된다.
• 위의 6가지 경우의 수에 대해서 각각 나머지 집들을 선택할 때의 최소값은 DP 배열을 통해 구할 수 있다.
• DP[i][색] 을 정하기 위해서는, DP[i-1] 의 3가지 색들 중 같은 색깔을 제외한 경우 중에, 1번 집이 고정됨으로써 강제적으로 불가능해지는 경로들을 제외한 색들을 고려해주면 된다.

---

 

import sys
N = int(input())
colors = [[0,0,0]] + [list(map(int, line.strip().split())) for line in sys.stdin]

if N == 2:
    print(min(colors[1][c1] + colors[2][c2] for c1 in range(3) for c2 in range(3) if c1 != c2))
else:
    points = [(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]      # 1번 집과 N번 집에 대한 제약을 미리 걸어두고 탐색
    answer = 10e9
    for begin, end in points:                           # 모든 조합을 탐색하면서 나머지 집들에 대해서는 DP 로 최소값 찾음
        dp = [[0,0,0] for i in range(N+1)]
        dp[1][begin] = colors[1][begin]                 # dp 배열에서 1번 집의 값은 미리 정해둔 색깔로만 칠해놓음
        for i in range(2, N):                           # 2번부터 N-1번 집까지 DP 채우기
            for c in range(3):
                lst = [dp[i-1][c2] for c2 in range(3) if (c2 != c and dp[i-1][c2] != 0)]            # 이전 집과 연속된 색깔이 아니며, 이전 집을 칠할 수 있었을 경우에만
                dp[i][c] = (min(lst) + colors[i][c]) if len(lst) else 0                             # DP 배열값이 0 이라는 것은 불가능한 경로라는 뜻
        tmp = min(dp[N-1][i] for i in range(3) if (i != end and dp[N-1][i] != 0)) + colors[N][end]  # 마지막 N 번 집의 색깔 칠해주고 최소값 갱신
        if tmp < answer:
            answer = tmp
    print(answer)