백준 1149번 파이썬 _ RGB거리

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

1149번: RGB거리

문제유형 : 다이나믹 프로그래밍

 

문제풀이 : 

 

1. 큰 문제를 작은문제로 쪼개서 생각해내는것이 필요

• 2번째 집을 파란색으로 색칠할때의 최솟값? -> 1번째집을 min(빨간색으로 색칠, 초록색으로 색칠) + 2번째집을 파란색으로 색칠할때의 비용 
• 그렇다면 3번째 집을 빨간색으로 색칠할때의 최솟값? -> 2번째집을 min(파란색으로 색칠, 초록색으로 색칠) --> 위에서 구했네??
• 작은문제의 반복 + 이전의 답이 그대로 이용 -> DP군!!

 

2. 작은 문제를 일반화시키는것

• i번째 집을 0으로(빨간색) 색칠할때의 최솟값 = i-1번째 집을 min(1로색칠, 2로 색칠) + i번째집을 0으로 칠할때 비용
• i번째 집을 1로 (초록) 색칠할때의 최솟값 = i-1번째 집을 min(0로색칠, 2로 색칠) + i번째 집을 1로 칠할때 비용
• i번째 집을 2로 (파랑) 색칠할때의 최솟값 = i-1번째 집을 min(0로 색칠, 1로 색칠) + i번째 집을 2로 칠할때 비용 

 

정답코드

import sys
input = sys.stdin.readline

#문제조건
#1번집과 2번집의 색은 달라야함
# N번집의 색은 n-1번집의 색과 달라야함
# i번째집은 i-1, i+1번쨰 집과 색이 달라야함
# 즉, 인접한 집의 색은 모두 달라야함

n = int(input())
graph = []
for i in range(n):
    line = list(map(int, input().split()))
    graph.append(line)

for i in range(1, len(graph)):
    # i번째집을 0(빨강), 1(초록), 2(파랑)으로 칠했을때의 최소값을 나타낸다.
    graph[i][0] = min(graph[i-1][1], graph[i-1][2])+graph[i][0]
    graph[i][1] = min(graph[i-1][0], graph[i-1][2])+graph[i][1]
    graph[i][2] = min(graph[i-1][0], graph[i-1][1])+graph[i][2]

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