백준 1149번: RGB거리

✔ 풀이를 위한 아이디어

• 다이나믹 프로그래밍 (Dynamic Programming)
  
  

✔ 수정 전 코드 [틀렸습니다]

import sys

N = int(sys.stdin.readline())
price = [-1]
dp = [-1, -1]

for _ in range(N):
    price.append(list(map(int, sys.stdin.readline().split())))

r = min(price[1][1]+price[2][0], price[1][2]+price[2][0])
g = min(price[1][0]+price[2][1], price[1][2]+price[2][1])
b = min(price[1][0]+price[2][2], price[1][1]+price[2][2])
tmp = min(r, g, b)
if tmp == r:
    dp.append((tmp, 0))
elif tmp == g:
    dp.append((tmp, 1))
else:
    dp.append((tmp, 2))

for i in range(3, N+1):
    if dp[i-1][1] == 0:
        g = dp[i-1][0]+price[i][1]
        b = dp[i-1][0]+price[i][2]
        tmp = min(g, b)
        if tmp == g:
            dp.append((tmp, 1))
        else:
            dp.append((tmp, 2))
    elif dp[i-1][1] == 1:
        r = dp[i-1][0]+price[i][0]
        b = dp[i-1][0]+price[i][2]
        tmp = min(r, b)
        if tmp == r:
            dp.append((tmp, 0))
        else:
            dp.append((tmp, 2))
    else:
        r = dp[i-1][0]+price[i][0]
        g = dp[i-1][0]+price[i][1]
        tmp = min(r, g)
        if tmp == r:
            dp.append((tmp, 0))
        else:
            dp.append((tmp, 1))

print(dp[N][0])

• 문제의 핵심은 잘 파악했다고 생각한다. 매 케이스마다 (N이 1씩 커질 때마다) 총 6가지 경우의 수가 생기는데, 이는 빨강으로 끝나는 경우, 초록으로 끝나는 경우, 그리고 파랑으로 끝나는 경우의 3가지로 분류할 수 있다. 이렇게 끝나는 색을 기준으로 분류하는 이유는, 문제의 조건에 의해서 이전에 끝난 색과 다른 색으로 칠해야하기 때문이다.
• 위의 코드는 그 3가지 경우 중에 최솟값만을 선택해서 다음으로 넘겨주었다. 하지만 N-1까지 최소로 칠하는 경우의 수를 따라갔다고 할지라도, 그것이 N번째에서도 최소라는 보장은 없으므로 위의 코드는 틀리게 된다.
  
  

✔ 수정 후 코드

import sys

N = int(sys.stdin.readline())
price = [-1]
dp = [-1]

for _ in range(N):
    price.append(list(map(int, sys.stdin.readline().split())))

dp.append((price[1][0], price[1][1], price[1][2]))

for i in range(2, N+1):
    r = min(dp[i-1][1]+price[i][0], dp[i-1][2]+price[i][0])
    g = min(dp[i-1][0]+price[i][1], dp[i-1][2]+price[i][1])
    b = min(dp[i-1][0]+price[i][2], dp[i-1][1]+price[i][2])
    dp.append((r, g, b))

print(min(dp[N][0], dp[N][1], dp[N][2]))

• 따라서, 서로 다른 색으로 끝날때의 3가지 최솟값들을 모두 다음으로 넘겨주도록 하였다. 이렇게 함으로써 매번 3가지 경우의 수를 고려하게 되고, 결과적으로 진정한 최솟값을 구할 수 있게 된다.
• 또한, N=2일 때도 for문 안에서 처리하도록 하여 코드가 훨씬 간결해지게 되었다.
  
  

✔ 관련 개념

• 다이나믹 프로그래밍 (Dynamic Programming)