[BOJ] 17404. RGB거리 2

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

접근

• 1149. RGB거리와 동일한 유형이나, N번 집과 1번집의 색이 달라야한다는 규칙이 추가되었다.
• 관건은 1번 집의 색을 기억하는 것이다. N번 집을 칠할 때, 1번 집에서 칠했던 색은 피해야한다.
• 이를 위해서는 1번 집에 R을 칠한 경우, G를 칠한 경우, B를 취한 경우 3개로 나누어 각각의 경우를 따로 확인해야한다.

과정

1. 최종 출력(답안)을 저장할 변수 answer를 따로 초기화한다.

2. input 데이터를 입력받는다.

3. 1번 집이 R, G, B인 경우를 고려해 3번 반복하는 for문을 돈다.
   3-1. 다이나믹 테이블을 초기화한다.

   dy[i][j]는 0,1,2...i까지 i번 집을 j색으로 칠했을 때의 최소 비용을 말한다.
   j=0 : R, j=1 : G, j=2 : B를 의미한다.
   최소비용을 구해야하므로 최대값으로 초기화한다.

   3-2. 1번 집에 칠할 색 비용을 dy[0]에 저장한다.
   3-3. for 반복문을 이용해 다이나믹 테이블을 채운다.
   3-4. N번 집까지 채웠으면 1번 집과 N번 집의 색이 동일한 경우를 제외한 최소 비용을 answer에 저장한다.

4. answer를 출력한다.

코드

import sys
input = sys.stdin.readline

# 1. 필요한 변수 초기화
INF = 2147000000
answer = INF

if __name__=="__main__":
	# 2. input 데이터 입력
    N = int(input())
    house = [list(map(int,input().split())) for _ in range(N)]
    # 3. R, G, B 각각의 경우로 반복문
    for i in range(3):
    	# 3-1. 다이나믹 테이블 초기화
        dt = [[INF] * 3 for _ in range(N)]
        # 3-2. 1번집에 칠할 비용을 다이나믹 테이블에 저장
        dt[0][i] = house[0][i]
        # 3-3. 다이나믹 테이블 채우기
        for j in range(1, N):
            dt[j][0] = min(dt[j-1][1], dt[j-1][2]) + house[j][0]
            dt[j][1] = min(dt[j-1][0], dt[j-1][2]) + house[j][1]
            dt[j][2] = min(dt[j-1][0], dt[j-1][1]) + house[j][2]
        # 3-4. 1번집과 N번집 색이 동일한 경우를 제외하고 최소 비용을 answer에 저장
        for k in range(3):
            if i == k:
                continue
            else:
                answer = min(answer, dt[-1][k])
    print(answer)