[백준] 1149 : RGB 거리 (파이썬)

DP 문제

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

 

💡 풀이 코드 (성공)

import sys 
n = int(sys.stdin.readline())
graph = [[0] * 3 for _ in range(n + 1)]
dp = [[0] * 3 for _ in range(n + 1)]

for i in range(1, n + 1):
    graph[i][0], graph[i][1], graph[i][2] = map(int, sys.stdin.readline().split())    
    if i == 1:
        dp[i][0],dp[i][1],dp[i][2] = graph[i][0],graph[i][1],graph[i][2]

def sol(n, graph):

    for i in range(2, n + 1):
        for j in range(3):
            if dp[i][j - 1] != 0:
                # dp[i][j] = min(dp[i][j - 1],  dp[i - 1][j - 1] + graph[i][j], dp[i - 1][j - 2] + graph[i][j]) # 이 코드의 문제점 -> 이전까지 누적된 dp값이 크면 현재 색상은 아예 안칠해버림. 하지만, 그 다음 입력을 고려할 때 현재 색상을 칠하는 경우가 더 유리한 경우가 있을 수 있음. 따라서, 무조건 색상을 다 칠한 후 마지막행에서 최솟값 비교 
                dp[i][j] = min(dp[i - 1][j - 1] + graph[i][j], dp[i - 1][j - 2] + graph[i][j])
            else:
                dp[i][j] = min(dp[i - 1][j - 1] + graph[i][j], dp[i - 1][j - 2] + graph[i][j])

    print(min(dp[n])) 

sol(n, graph)

 

dp[i][j] = i번째 집을 j번째 색으로 칠할 때의 비용의 최솟값 

초기 코드 문제점

초기 코드에서의 점화식은 다음과 같다.

 

dp[i][j] 

= min(dp[i][j - 1],  dp[i - 1][j - 1] + graph[i][j], dp[i - 1][j - 2] + graph[i][j])

= min(현재 집을 칠할 때 j번째 색을 사용하지 않을 경우의 누적된 최소 비용,
이전 집을 j - 1번째 색깔로 칠할 경우의 누적된 최소 비용 + 현재 집을 j번째 색깔로 칠할 경우의 비용,
이전 집을 j - 2번째 색깔로 칠할 경우의 누적된 최소 비용 + 현재 집을 j번째 색깔로 칠할 경우의 비용)

 

-> 즉, 현재 집을 칠할 때 j번째 색을 사용하지 않는 경우가 비용이 더 적다면 현재 집을 칠하는데 j번째 색상을 아예 사용하지 않는다.

하지만, 그 다음 입력을 고려할 때 현재 집을 j번째 색상으로 칠하는 경우가 더 유리한 경우가 있을 수 있다.

따라서, dp[i][j]에는 무조건 j번째 색으로 집을 칠할 때의 비용의 최솟값을 기록하고, 마지막 행에서 dp[n][0], dp[n][1], dp[n][2] 사이의 최솟값을 비교하여 답을 출력해야 한다.

if dp[i][j - 1] != 0:
    dp[i][j] = min(dp[i][j - 1],  dp[i - 1][j - 1] + graph[i][j], dp[i - 1][j - 2] + graph[i][j]) # 코드의 문제점

 

주요 로직

dp[i][j]

= min(dp[i - 1][j - 1] + graph[i][j], dp[i - 1][j - 2] + graph[i][j])

= min(이전 집을 j - 1번째 색깔로 칠할 경우의 누적된 최소 비용 + 현재 집을 j번째 색깔로 칠할 경우의 비용,
이전 집을 j - 2번째 색깔로 칠할 경우의 누적된 최소 비용 + 현재 집을 j번째 색깔로 칠할 경우의 비용)

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

 

마지막 행을 빨간색/초록색/파란색으로 칠할 경우의 누적된 최소 비용을 비교하여 최솟값을 출력한다.

print(min(dp[n]))