[BOJ, 백준] 17404 RGB 거리 2

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

 

 

 

해답코드는 아래와 같다.

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

def f(N, cost):
    if N == 2:
        return min(cost[0][0] + cost[1][1], cost[0][0] + cost[1][2], cost[0][1] + cost[1][2], cost[0][1] + cost[1][0], cost[0][2] + cost[1][0], cost[0][2] + cost[1][1])
    else:
        #dpi_j는 시작이 i고 마지막이 j색인 것
        dp1_2, dp1_3 = [cost[0][0], cost[0][0] + cost[1][1]], [cost[0][0], cost[0][0] + cost[1][2]]
        dp2_1, dp2_3 = [cost[0][1], cost[0][1] + cost[1][0]], [cost[0][1], cost[0][1] + cost[1][2]]
        dp3_1, dp3_2 = [cost[0][2], cost[0][2] + cost[1][0]], [cost[0][2], cost[0][2] + cost[1][1]]
        dp1_1, dp2_2, dp3_3 = [], [], []
        for i in range (3, N + 1):
            x1_2, x1_3 = dp1_2[-1], dp1_3[-1]
            x2_1, x2_3 = dp2_1[-1], dp2_3[-1]
            x3_1, x3_2 = dp3_1[-1], dp3_2[-1]

            if dp1_1 == []:
                dp1_1.append(min(x1_2, x1_3) + cost[i - 1][0])
                dp2_2.append(min(x2_1, x2_3) + cost[i - 1][1])
                dp3_3.append(min(x3_1, x3_2) + cost[i - 1][2])

                dp1_2.append(x1_3 + cost[i-1][1])
                dp1_3.append(x1_2 + cost[i-1][2])
                dp2_1.append(x2_3 + cost[i-1][0])
                dp2_3.append(x2_1 + cost[i-1][2])
                dp3_1.append(x3_2 + cost[i-1][0])
                dp3_2.append(x3_1 + cost[i-1][1])
            else:
                dp1_2.append(min(dp1_1[-1], x1_3) + cost[i - 1][1])
                dp1_3.append(min(dp1_1[-1], x1_2) + cost[i - 1][2])
                dp2_1.append(min(dp2_2[-1], x2_3) + cost[i - 1][0])
                dp2_3.append(min(dp2_2[-1], x2_1) + cost[i - 1][2])
                dp3_1.append(min(dp3_3[-1], x3_2) + cost[i - 1][0])
                dp3_2.append(min(dp3_3[-1], x3_1) + cost[i - 1][1])

                dp1_1.append(min(x1_2, x1_3) + cost[i - 1][0])
                dp2_2.append(min(x2_1, x2_3) + cost[i - 1][1])
                dp3_3.append(min(x3_1, x3_2) + cost[i - 1][2])

        return min(dp1_2[-1], dp1_3[-1], dp2_1[-1], dp2_3[-1], dp3_1[-1], dp3_2[-1])


print(f(N, cost))

 

 

Dp 문제인데, 이러한 점화식 계열로 나오는 문제들의 경우에는 케이스를 잘 나누어 주는 것이 키포인트 같다.

array의 네이밍에서부터, 처음 시작 색 - 마지막 색을 정하는 것이 가능하다. (단 6가지에 불과하다.)

 

문제를 풀면서 3번째 예제에서 많이 막혔었는데, 이때 i_i로 나타내지는 array를 계산하지 않았던 것이 컸던 것 같다.

i_i인 array는 실제 문제의 답에서 나오지는 않지만, 징검다리 역할이라고 해야하나.

도중 관계에서 나오게 되겠다.