[ 백준 ][ 골드4 ] 17404번 - RGB거리2 ( 파이썬 Python )

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

17404번: RGB거리 2

 

문제

---

 

코드

---

import sys
input = sys.stdin.readline
INF = 2147000000
n = int(input())
rgb = []
ans = INF
for _ in range(n):
    rgb.append(list(map(int, input().split())))

for i in range(3):
    dp = [[INF, INF, INF] for _ in range(n)]
    dp[0][i] = rgb[0][i]
    for j in range(1, n):
        dp[j][0] = rgb[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = rgb[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = rgb[j][2] + min(dp[j-1][0], dp[j-1][1])

    for j in range(3):
        if i != j:
            ans = min(ans, dp[-1][j])
print(ans)

 

풀이

---

처음에는 DFS로 해결하고 제출했지만 45%에서 시간초과를 맞게 되었다.

처음 작성했던 코드는 다음과 같다.

import sys
imput = sys.stdin.readline

def DFS(idx,prev,prefix,start):
    global answer

    if prefix >= answer:
        return
    
    if idx == n-2:
        for i in range(3):
            if i not in (prev,start):
                answer = min(answer, prefix+arr[-1][i])
        return

    for i in range(3):
        if i == prev:
            continue
        DFS(idx+1,i,prefix+arr[idx+1][i],start)

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
answer = 1e9

for i in range(3):
    DFS(0,i,arr[0][i],i)

print(answer)

 

DP로 해결하려면 이전 집에서 칠한 색을 제외한 나머지 두 색깔 중 더 작은 값을 가지고 오는 점화식을 사용하는데

맨 마지막 인덱스에 도달했을 때가 문제이다.

맨 마지막 인덱스에 도달하면 맨 처음 집에서 칠한 색을 고려해야 하는데 DP에서 그 값을 가지고 움직일 수는 없다.

 

그래서 맨 처음 집의 색을 정하고 DP탐색을 시작하는 방식으로 변경했다.

맨 처음 집이 빨강일때, 초록일때, 파랑일떄 총 3번 DP탐색을 하면 맨 마지막 집을 칠할 때도 문제없이 색을 정할 수 있다.