[BOJ] 17404번 - RGB거리 2

---

문제설명

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

17404번: RGB거리 2

사고과정

• RGB 거리 문제와 비슷한 유형이긴 했지만 첫 집과 마지막 집 조건이 달라야 하는 조건이 추가 되었다. 이를 어떻게 처리할 수 있을지 매우 고민했다..처음에 DP 테이블 요소에 맨 처음 집 위치를 넣어주어야 하나 싶었는데 너무 복잡해지는 것 같아 아닌 것 같았다..
• 풀이를 보니 처음 집의 색깔 3종류에 따라 개별로 탐색을 수행했다. 문제를 푸는 단계는 다음과 같다.

1. 주어지는 색깔 비용 테이블과 DP 테이블을 개별로 운영
2. DP 테이블을 첫 색깔 경우에 따라 갱신하고 초기화
3. DP 테이블 갱신(이 때 갱신시 비용 테이블을 참고하면서 진행)
4. 마지막에 첫 색깔과 다를 경우만 최솟값 갱신(마지막 색깔은 첫 색깔과 인덱스가 같지 않을 경우, 첫 색깔과 다른 색깔을 썼음을 의미한다. 또 마지막 행의 특정 열 값은 마지막 집은 그 특정 색깔을 이용했다는 것이나 마찬가지를 의미한다)

풀이(스스로 못 푼 풀이)

n = int(input())
cost = []
for _ in range(n):
    cost.append(list(map(int, input().split())))
INF = float('inf')
result = INF

for init in range(3):
    dp = [[0] * 3 for _ in range(n)]
    # DP 테이블의 첫째 집 색깔 갱신
    for j in range(3):
        if j == init:
            dp[0][j] = cost[0][j]
            continue
        dp[0][j] = INF
    # DP 테이블 갱신
    for i in range(1, n):
        dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
        dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])
    # 마지막 집과 첫재 집 색깔 같으면 무시!
    for j in range(3):
        if j == init:
            continue
        result = min(result, dp[-1][j])

print(result)