백준 / RGB거리 2 / 17404번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: RGB거리 2 / 17404번 (골 4단계)

문제 사이트: https://www.acmicpc.net/problem/17404

 

문제 설명

---

나의 풀이

import sys

def main():
    n = int(sys.stdin.readline())
    home = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    INF = int(1e9)
    result = INF

    # 0: R, 1: G, 2: B
    for first_color in range(3):
        dp = [[INF] * 3 for _ in range(n)]
        # 첫 번째 집은 첫 색만 선택 가능
        dp[0][first_color] = home[0][first_color]

        for i in range(1, n):
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + home[i][0]
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + home[i][1]
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + home[i][2]

        # 마지막 집은 첫 번째 색과 다른 색만 고려
        for last_color in range(3):
            if last_color != first_color:
                result = min(result, dp[n-1][last_color])

    print(result)


if __name__ == "__main__":
    main()

---

※ 알아야 할 것

DP를 이용하여 문제를 해결하시면 됩니다.

# 마지막 집은 첫 번째 색과 다른 색만 고려
        for last_color in range(3):
            if last_color != first_color:
                result = min(result, dp[n-1][last_color])

이 코드는 문제 조건에 따라 마지막 집은 첫 번째 집과 다른 색을 고려해야 하므로 꼭 적어주셔야 합니다.