[Python]백준 1149번/RGB거리/dp

 

# 문제 설명 

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

1149번: RGB거리

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

# 해결 방법

 

dp[0]자리는 1번 집

dp[1]자리는 2번 집

dp[3]자리는 3번 집

 

i=0일 때는 1번집이 각각 R일 경우 G일경우 B일경우 이다. 그러므로 26,40,83이 그대로 들어간다.

i=1 일 때는 2번집이 각각 R일 경우 G일경우 B일경우 이다. 

**이 때는 2번집이 🔴일 경우**

-> 1번집이 🟢인 경우의 비용과 1번집이 🔵인 경우의 비용 중에 작은 값을 2번 집이 🔴인경우의 비용을 더해준다. 

ex) dp[i][0] = min(dp[i-1][1], dp[i-1][2])+info[i][0]

**이 때는 2번 집이 🟢일 경우**

-> 1번집이 🔴인 경우의 비용과 1번집이 🔵인 경우의 비용 중에 작은 값을 2번 집이 🟢인경우의 비용을 더해준다. 

ex) dp[i][1] = min(dp[i-1][0], dp[i-1][2])+info[i][1]

**이 때는 2번 집이 🔵일 경우**

-> 1번집이 🔴인 경우의 비용과 1번집이 🟢인 경우의 비용 중에 작은 값을 2번 집이 🔵인경우의 비용을 더해준다. 

ex) dp[i][2] = min(dp[i-1][0], dp[i-1][1])+info[i][2]

 

.... 반복 !

 

 

# 코드

n=int(input())
info=[]
for _ in range(n):
    r,g,b=map(int,input().split())
    info.append([r,g,b])


dp=[[0]*3 for _ in range(n)]

for i in range(n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2])+info[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2])+info[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1])+info[i][2]

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