[백준-파이썬] 17404: RGB거리 2

문제로~

RGB거리 1을 풀고, RGB 거리 2도 있길래 스터디 문제에 넣었다.
RGB 거리 1은 괜찮았는데,,, 이 문제는 좀 더 생각을 해야 한다.

달라진 거라고는 1번 집 색깔과 마지막 집 색깔이 달라야 한다는 것 뿐이다. 그런데 훨씬 어렵다..ㅠ 아이디어가 잘 안떠올랐다..

1번 집의 색깔을 기억(?)하고 있어야 한다는 거니까, R, G, B 각각에서 출발해 보면 된다. 또 첫번째 집과 마지막 집 색깔이 달라야 하니까, 정답(ans)을 구할 때 마지막 집을 R, G, B로 색칠한 결과(첫번째~마지막 집 색칠한 최소 비용) 중 첫번째 집과 색깔이 같은 건 고려하지 않아야 한다.

R, G, B 각각에서 출발하는 것을 구현하려면.. => 다른 곳의 값은 크게 두고, 해당 색깔으로 칠하는 경우만 그 때 필요한 비용으로 두면 된다. 무조건 해당 색깔에서 출발하는 게 최소 비용이라서, 그 곳에서 출발하는 셈이 된다.

그 후로는 RGB 거리 1 풀 때와 같다. 집을 특정 색깔로 칠하려고 할 때, 그 바로 전 집만 다른 색깔이면 된다. (그래서 dp 리스트를 크게 잡지 않고 2로만 잡았다. ) 예를 들어서 지금 R로 칠하려고 하면, '그 전 집이 G일 때 그때까지의 비용 더한 것'과 '그 전 집이 B일 때 그때까지의 비용 더한 것' 중 적은 것 + 지금 R로 칠할 때 비용을 더해서, 그 집을 R로 칠할 때 최소 비용으로 업데이트하면 된다.지금 집을 각각 색으로 칠할 때 최소 비용을 다 업데이트 했으면, 그 집을 이전 집으로 생각해야 하니까 dp[0][0], dp[0][1], dp[0][2] = dp[1][0], dp[1][1], dp[1][2] 이렇게 했다.

마지막 집까지 칠한 뒤에는, 마지막 집을 첫번째 집과 다르게 색칠한 두 경우(그렇게 칠하기까지 든 비용)를 보았다. ans과 비교하면서 더 적으면 ans으로 업데이트했다.

import sys
input = sys.stdin.readline

INF = 1000 * 1000 * 10
N = int(input())
house_color_costs = list(list(map(int, input().split())) for _ in range(N))

dp = [[0] * 3 for _ in range(2)]  # 각 집이 각 색깔(빨, 초, 파)로 칠해졌을 때의 최소 비용

ans = INF

for k in range(3):  # RGB 각각 시작하는 경우
    # 첫번째 집 칠할 때 - R, G, B 각각에서 시작하기 위해서 초기화
    dp[0][0], dp[0][1], dp[0][2] = INF, INF, INF
    dp[0][k] = house_color_costs[0][k]

    for i in range(1, N):  # 두번째 집부터 다음 집과 색깔 다르게 쭉~~~
        dp[1][0] = min(dp[0][1], dp[0][2]) + house_color_costs[i][0] 
        dp[1][1] = min(dp[0][0], dp[0][2]) + house_color_costs[i][1]
        dp[1][2] = min(dp[0][0], dp[0][1]) + house_color_costs[i][2]

        dp[0][0], dp[0][1], dp[0][2] = dp[1][0], dp[1][1], dp[1][2]

    ans = min(ans, min(dp[0][(k + 1) % 3], dp[0][(k + 2) % 3]))  # 1번 집과 마지막 집 색깔 같은 경우는 빼고, 필요하면 정답 업데이트

# 정답
print(ans)