[백준 1149번] 파이썬 - RGB 거리

백준 1149_RGB 거리

조건

• 집이 N개가 있고, 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
• 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.
• 각 집을 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하라.
  • 1번 집의 색은 2번 집의 색과 같지 않아야한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i (2<= i <= N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

접근 방법

• 각 색깔이 사용되었을 때의 최소비용을 기록할 DP TABLE을 만들어준다.
• 이전 집이 사용하지 않은 색 중에서 최소비용만 뽑아서 비교해보면 된다.
• 즉, 첫 번째 집이 빨강이라면, 두 번째 집이 파랑과 초록을 선택했을 때, 최소 값을 구해서 기록해주면 된다.
• 모든 비교가 끝난 후 마지막 집의 최소 비용을 출력해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  


# dp로 풀어주기  
# 첫 집 색칠 모든 집 -> 이후 첫 집 색과 다른 색깔들을 더해가면 된다.  
# 빨강 - 0, 초록 - 1, 파랑 - 2 의 인덱스 번호 사용  
# 2번째 집부터는 i-1번째의 현재 집 색칠 비용 + i번 째 색칠 비용 중 인덱스가 다른 색깔과의 합 중 최소값을 기록  
N = int(input())  
dp = [[0, 0, 0] for _ in range(N)]  
cost = [[*map(int, input().split())] for _ in range(N)]  

# 첫 집 초기화  
dp[0] = cost[0]  

# 두 번째 집 부터 순회  
for i in range(1, N):  
    # 3가지 색깔 갱신해주면서 기록해주기  
    for j in range(3):  
        dp[i][j] = min(dp[i-1][j-1] + cost[i][j], dp[i-1][j-2] + cost[i][j])  

print(min(dp[-1]))