DP) 1149.RGB 거리

문제

1149. RGB 거리

[1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net](https://www.acmicpc.net/problem/1149)

규칙

1. 집을 빨강, 파랑, 초록 중 하나로 칠한다.
2. 모든 이웃은 같은 색으로 칠할 수 없다.
3. 집 i의 이웃은 i-1, i+1 이고, 첫 집과 마지막 집은 이웃이 아니다.

목표

각 집을 각 색으로 칠하는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하라.

Solution

1. a[i][j] : i번 집을 j번 색으로 칠하는 비용
2. d[i][j] : i번 집을 j번 색으로 칠했을 때, 1~i번 집을 칠하는 비용의 최솟값
3. j : 0(빨강) , 1(초록) , 2(파랑)
4. 점화식 : d[i][0] = min(d[i-1][1],d[i-1][2]) + a[i][0]
   ex) i번 집을 0으로 색칠했을 때, i-1번 집을 1 or 2 로 색칠할 수 있고, 그 때 i-1번 집까지 색칠하는 비용의 최솟값을 구하고 거기에 i번 집을 0으로 칠하는 비용을 더한다.
5. 4번 프로세스를 0,1,2 모두 적용
6. 마지막 집에 어떤 색을 칠한 경우가 최솟값인 지 알 수 없으므로, min(d[n][0],d[n][1][,d[n][2]) 가 정답이다.

소스 코드

n=int(input())  

a = [[0,0,0]] + [list(map(int,input().split()))for _ in range(n)]  

d=[[0,0,0] for _ in range(n+1)]  

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

print(min(d[n][0],d[n][1],d[n][2]))