[Python] 백준 - 17404 RGB거리 2

백준 - 17404 RGB거리 2

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

필요한 도구

 

 

1. DP 리스트 = [[R, G, B] for _ in range(n)]

 

 

문제해결방법

 

 

1. 문제에도 쓰여있지만, 각 R, G, B에 해당하는 DP에 저장되어야 하는 값의 규칙은 다음과 같다.

 

1) 최소값일 것.

2) 'R'을 선택했다면 전 후로 'R'을 선택하면 안될 것.

3) 첫 시작 색깔과 마지막 색깔이 같지 않을 것.

 

2. DP[0]에 주어진 RGB값들을 넣고, 시작점을 명시하며, 그 전의 다른 색깔의 값과 현재 선택한 색깔의 값의 최소값이 누적되도록 한다.

 

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

 

- DP에 최소값이 누적되는 방식

 

3. DP를 구해준 후, 처음에 명시된 시작점과 같지 않은 값들만 비교하여 최소값을 구한다.

 

- 코드

import sys
input = sys.stdin.readline

n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
INF = sys.maxsize
ans = INF

for start in range(3):
    dp = [[INF for _ in range(3)] for _ in range(n)]
    dp[0][start] = d[0][start]
    for i in range(1, n):
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + d[i][0]
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + d[i][1]
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + d[i][2]
    for last in range(3):
        if last != start:
            ans = min(ans, dp[n-1][last])
print(ans)