알고리즘 - Python / 백준 - 17404번 : RGB거리 2

17404번: RGB거리 2 (acmicpc.net)

17404번: RGB거리 2

 

---

풀이

• RGB 거리 1 문제에 1번째 집과 마지막 집의 색이 다르게 해야 한다는 조건만 추가된 문제다.
• RGB 문제 역시 점화식을 통해 DP로 해결가능한 문제이므로 DP로 접근해 문제를 풀었다.
• RGP 거리 1 문제와 다른점은 선택 가능한 마지막 집이 첫 번째 집과 색이 겹치지 않아야 한다는 것이다.
• 따라서 DP 배열을 3개 만들어 첫번째 집이 R , G  , B 인 경우로 두고 모두 구하였다.
• 이렇게 하면 마지막에 선택할 집 색이 2개로 정해지고 , 그 2개 중 여태까지 구한 부분 문제의 합 + 그 집의 비용이 MIN이 되는 경우를 찾으면 된다.
• 위 과정을 통해서 첫번째 집이 R , G , B 인 경우의 3가지 MIN값이 나올 것이고 이 3개의 MIN 값 중 최종 MIN값을 구해 출력하면 된다.
• 단순하게 아이디어대로 풀어 코드가 많이 지저분 하다. 아이디어는 살린 채로 코드를 간결하게 쓰는 방법도 생각해 보아야 할 듯싶다. ( EX : DP1 , DP2 , DP3이 아니라 3차원 DP 배열을 통해 for문으로 묶기 )

 

import sys
n = int(sys.stdin.readline())
s = []
for _ in range(n):
    s.append(list(map(int, sys.stdin.readline().split(" "))))
dp_1 = [[0 for i in range(3)] for t in range(n)]
dp_2 = [[0 for i in range(3)] for t in range(n)]
dp_3 = [[0 for i in range(3)] for t in range(n)]

dp_1[0][0] , dp_1[0][1] , dp_1[0][2]  = s[0][0] , (10**6) + 1, (10**6) + 1
dp_2[0][1] , dp_2[0][0] , dp_2[0][2]  = s[0][1] , (10**6) + 1, (10**6) + 1
dp_3[0][2] , dp_3[0][1] , dp_3[0][0]  = s[0][2] , (10**6) + 1, (10**6) + 1

for i in range(1,n-1):
    dp_1[i][0] = min(dp_1[i - 1][1], dp_1[i - 1][2]) + s[i][0]
    dp_1[i][1] = min(dp_1[i - 1][2], dp_1[i - 1][0]) + s[i][1]
    dp_1[i][2] = min(dp_1[i - 1][1], dp_1[i - 1][0]) + s[i][2]

for i in range(1,n-1):
    dp_2[i][0] = min(dp_2[i - 1][1], dp_2[i - 1][2]) + s[i][0]
    dp_2[i][1] = min(dp_2[i - 1][2], dp_2[i - 1][0]) + s[i][1]
    dp_2[i][2] = min(dp_2[i - 1][1], dp_2[i - 1][0]) + s[i][2]

for i in range(1,n-1):
    dp_3[i][0] = min(dp_3[i - 1][1], dp_3[i - 1][2]) + s[i][0]
    dp_3[i][1] = min(dp_3[i - 1][2], dp_3[i - 1][0]) + s[i][1]
    dp_3[i][2] = min(dp_3[i - 1][1], dp_3[i - 1][0]) + s[i][2]


dp_1[n-1][1] = min(dp_1[n - 2][2], dp_1[n - 2][0]) + s[n-1][1]
dp_1[n-1][2] = min(dp_1[n - 2][1], dp_1[n - 2][0]) + s[n-1][2]
dp_1_min = min(dp_1[n-1][1] , dp_1[n-1][2])

dp_2[n-1][0] = min(dp_2[n - 2][1], dp_2[n - 2][2]) + s[n-1][0]
dp_2[n-1][2] = min(dp_2[n - 2][1], dp_2[n - 2][0]) + s[n-1][2]
dp_2_min = min(dp_2[n-1][0] , dp_2[n-1][2])

dp_3[n-1][1] = min(dp_3[n - 2][2], dp_3[n - 2][0]) + s[n-1][1]
dp_3[n-1][0] = min(dp_3[n - 2][1], dp_3[n - 2][2]) + s[n-1][0]
dp_3_min = min(dp_3[n-1][1] , dp_3[n-1][0])

print(min(dp_3_min,dp_2_min,dp_1_min))

---