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

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

17404번: RGB거리 2

DP 문제인데 정말 어려웠다.

 

이 문제는 RGB거리 와 비슷한데, 마지막 집과 첫번째 집이 인접한 원형 형태로 구성되어 있다고 한다.

그래서 마지막 답을 구할때, 첫번째에 어떤 집을 선택했나를 확인해야 한다.

 

dp 배열의 의미는 다음과 같다

dp[RGB 색, 각각 0,1,2] [ 0-(n-1)번째 집] 이다.

 

일단, 처음에 어떤 색을 선택했나 R,G,B 다 돌아볼 수밖에 없다.

initcolor 를 각각 0,1,2 즉 R,G,B 로 해서 for 문을 돌린다.

그리고, dp 배열의 첫번째 원소는 initcolor는 input 값과 같게, 나머지는 엄청 큰 수로 선택한뒤,  RGB거리  처럼 하면 된다.

 

그리고 첫번째로 선택한 각각의 선택지에 대해 최솟값을 구해서 답을 제출하면 된다.

이때도, 3개의 마지막 배열값중 initcolor와 같은 선택지는 빼줘야한다.

 

참고로, 912344123412 이런숫자는 의미없는 큰숫자다. 

https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number

Nothing-up-my-sleeve number - Wikipedia

맨날 up ,on 헷갈린다. 블로그 어디에는 on으로 적혀있을듯

import sys

n = int(input())

m = []

for _ in range(n):
    m.append([int(i) for i in sys.stdin.readline().split()])


ret = 99123443214231

for initcolor in range(3): 

    dp = [[0 for _ in range(n)] for _ in range(3)]

    for i in range(3): 
        if i == initcolor:
            dp[i][0] = m[0][i]
            continue
        dp[i][0] = 9123443214231

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

    
    for i in range(3): 
        if i == initcolor:
            continue
        ret = min(ret, dp[i][-1])


print(ret)