문제

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

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

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

입력

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

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이방법

키워드 : DP
일단 조건은 3가지가 있지만 사실 3번 조건만 만족하면 1,2번은 만족하기에 3번조건에만 집중하였다.
바텀업 방식으로 접근을 하여 풀었다. for문을 돌리면서 색깔별로 이전 색깔과 비교하여 min값을 찾아서 각 색깔별로 넣어주는 식으로 구현을 하였다. 코드를 보면 바로 이해가 갈것이다.

소스코드

import sys

n = int(sys.stdin.readline())

graph=[]

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

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

for i in range(3):
    dp[0][i]=graph[0][i]

# 각 색깔별로 이전의 dp값과 비교하여 min값을 찾고 겹치지 않도록 인덱스를 조정
for i in range(1,n):
    dp[i][0]=min(dp[i-1][1]+graph[i][0],dp[i-1][2]+graph[i][0])
    dp[i][1]=min(dp[i-1][0]+graph[i][1],dp[i-1][2]+graph[i][1])
    dp[i][2]=min(dp[i-1][0]+graph[i][2],dp[i-1][1]+graph[i][2])

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