[Python] 백준 1149번. RGB거리

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

1149번: RGB거리

문제설명

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

풀이설계

• DP(다이나믹 프로그래밍)을 이용해 앞에서부터 최소값을 저장해나가며 모든 집을 칠했을 때 최소값을 구하는 문제이다.
• DP용 2차원 배열을 하나 더 만들어준다.
• 첫번째에서는 RGB를 모두 선택할 수 있다.
• 두번째부터는 선택의 조건이 달라진다
  • R을 선택했을 경우 GB만 선택가능하다. 
  • G을 선택했을 경우 RB만 선택가능하다.
  • B을 선택했을 경우 RG만 선택가능하다.

import sys

input = sys.stdin.readline
n = int(input())
cost = []
# 첫번째에서는 RGB를 모두 선택할 수 있다.
dp = [[0]*3 for _ in range(n)]
for i in range(n):
    cost.append(list(map(int, input().split())))

dp[0][0], dp[0][1], dp[0][2] = cost[0][0], cost[0][1], cost[0][2]

for i in range(1, n):
	# R을 선택했을 경우 GB만 선택가능하다. 
    dp[i][0] = min(dp[i-1][1]+cost[i][0], dp[i-1][2]+cost[i][0])
    # G을 선택했을 경우 RB만 선택가능하다.
    dp[i][1] = min(dp[i-1][0]+cost[i][1], dp[i-1][2]+cost[i][1])
    # B을 선택했을 경우 RG만 선택가능하다.
    dp[i][2] = min(dp[i-1][0]+cost[i][2], dp[i-1][1]+cost[i][2])

print(min(dp[n-1][0], dp[n-1][1], dp[n-1][2]))