17404(RGB거리 2) - 해결

RGB거리 2

 

문제

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

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

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

 

입력

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

 

출력

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

---

RGB거리 의 다음 단계인 문제였다.

전과 달리 1번집과 N번집의 색깔도 달라야했다.

그래서 어떻게 할까 생각하였다.

사이에 집은 전과 비슷하지만 처음집과 N번째 집이 다르게 할 방법을 생각했을때 

각 색깔마다 dp를 만들기로 하였다.

그리고 이를 위해 무한대를 지정하여 해당 색을 선택하지 못하게 저장해주었다.

import sys
iuput = sys.stdin.readline

N = int(input())

maps = [list(map(int,input().split())) for _ in range(N)]

INF = 987654321
# 처음을 각 R, G, B를 선택했을 때 각각 dp로 저장
# 그러면 2번째는 각각 R, G, B를 선택할 수 없기 때문에 무한으로 저장
Rdp = [maps[0],[INF,maps[0][0]+maps[1][1],maps[0][0]+maps[1][2]]]
Gdp = [maps[0],[maps[0][1]+maps[1][0],INF,maps[0][1]+maps[1][2]]]
Bdp = [maps[0],[maps[0][2]+maps[1][0],maps[0][2]+maps[1][1],INF]]

# 그 다음 전과 같이 비교하면 dp에 저장
for i in range(2,N):
    # 마지막은 2번째처럼 각각 R, G, B를 선택 못하기 때문에 
    # 무한으로 저장
    if i == N-1:
        Rdp.append([INF,min(Rdp[i-1][0],Rdp[i-1][2]) + maps[i][1],min(Rdp[i-1][1],Rdp[i-1][0]) + maps[i][2]])
        Gdp.append([min(Gdp[i-1][1],Gdp[i-1][2]) + maps[i][0],INF,min(Gdp[i-1][1],Gdp[i-1][0]) + maps[i][2]])
        Bdp.append([min(Bdp[i-1][1],Bdp[i-1][2]) + maps[i][0],min(Bdp[i-1][0],Bdp[i-1][2]) + maps[i][1],INF])
    # 나머지는 그대로 저장
    else:
        Rdp.append([min(Rdp[i-1][1],Rdp[i-1][2]) + maps[i][0],min(Rdp[i-1][0],Rdp[i-1][2]) + maps[i][1],min(Rdp[i-1][1],Rdp[i-1][0]) + maps[i][2]])
        Gdp.append([min(Gdp[i-1][1],Gdp[i-1][2]) + maps[i][0],min(Gdp[i-1][0],Gdp[i-1][2]) + maps[i][1],min(Gdp[i-1][1],Gdp[i-1][0]) + maps[i][2]])
        Bdp.append([min(Bdp[i-1][1],Bdp[i-1][2]) + maps[i][0],min(Bdp[i-1][0],Bdp[i-1][2]) + maps[i][1],min(Bdp[i-1][1],Bdp[i-1][0]) + maps[i][2]])

# 이렇게 마지막에 R, G, B를 선택했을 때 가장 작은 값이 답
print(min(Rdp[-1]+Gdp[-1]+Bdp[-1]))