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

0.  문제 링크

 

 

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

17404번: RGB거리 2

---

1.  풀이 방법

 

 

일단 문제를 보자마자 이건 DP라는 생각이 들었다.

가장 문제는 마지막 집과 첫 번째 집의 색이 달라야 한다는 것이다.

사실 마지막 집과 첫 번째 집의 색을 고려하지 않고 짰는데, 알고 보니 고려해야 해서 조금 수정을 했다.

그러면 고려를 한다면 어떻게 해야할까?

많은 고민을 했다. 누가 봐도 DP인데, 어떻게 첫 번째 집의 정보를 저장해야 할지 좀 헷갈렸다.

결론은 첫 번째 집을 픽스하고 찾는 것!

첫 번째 집을 0번째로 골랐을 때, 1번째로 골랐을 때, 2번째로 골랐을 때, 하나하나 나누어서 고려하니까 생각보다 쉽게 풀렸다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    maps = [list(map(int, input().split())) for _ in range(n)]
    dp = [[float('inf')] * 3 for _ in range(n)]
    dir = [[0, 1, 2], [1, 0, 2], [2, 0, 1]]
    mins = float('inf')

    for start in range(3):      # 시작을 달리하기 위하여
        dp[0] = [float('inf')] * 3
        dp[0][start] = maps[0][start]

        for row in range(1, n):     # 최솟값으로 갱신함
            for i, j, k in dir:
                dp[row][i] = maps[row][i] + min(dp[row - 1][j], dp[row - 1][k])

        for end in range(3):
            if start != end:        # 시작과 다를 경우에만 최솟값을 갱신함
                mins = min(mins, dp[n - 1][end])

    print(mins)

---

3.  마무리