[BOJ] 1149번 - RGB거리

---

문제설명

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

1149번: RGB거리

사고과정

• 문제에서 갑자기 거리는 선분으로 나타낼 수 있다는 말에 선분이 간선인가 싶어서 엥 그래프 알고리즘인가..? 했지만 문제를 더 읽어보니 선분은 중요치 않았다. 전형적인 DP 테이블을 2차원 리스트로 운영하는 문제였다.
• 단, 조건이 있었는데 서로 인접한 집들끼리는 무조건 다른 색깔을 칠해야 하는 것이었다. 따라서 이를 기반으로 점화식을 구현하면 된다. 처음에 DP 테이블과 색깔 별 드는 비용을 따로 운영했어야 하나 했는데 연습장에 1개 예시를 들어보고 바로 DP테이블 하나로 운영하면 될 수 있구나 이해했다. 
• 어차피 빨강, 초록, 파랑 3개니까 DP 테이블의 행($i$)는 N을, 열($j$)는 각각 빨강, 초록, 파랑이라고 생각하고 다이나믹 프로그래밍을 수행하면 된다. 점화식은 집을 어떤 색깔로 칠하느냐에 따라 점화식이 약간씩 달라진다. 즉, DP 테이블 상에서 1번째 행(두 번째 집을 의미)에서 빨간색 집을 선택할 것이냐, 초록색 또는 파란색을 선택할 것이냐에 따라 점화식이 아래 처럼 달라진다. 구체적인 점화식은 소스코드에서 살펴볼 수 있다.

풀이

n = int(input())
dp = []
for _ in range(n):
    dp.append(list(map(int, input().split())))

for i in range(1, n):
    for j in range(0, 3):
        # R선택
        if j == 0:
            dp[i][j] = dp[i][j] + min(dp[i-1][1], dp[i-1][2]) # min(초록, 파랑)
        if j == 1:
            dp[i][j] = dp[i][j] + min(dp[i-1][0], dp[i-1][2]) # min(빨강, 파랑)
        if j == 2:
            dp[i][j] = dp[i][j] + min(dp[i-1][0], dp[i-1][1]) # min(빨강, 초록)

print(min(dp[n-1]))