1149번 RGB거리

문제

https://www.acmicpc.net/problem/1149
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

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

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

풀이

답을 하나하나 구해야하는데 그 중에서 최적의 답을 찾으려면 DP로 푸는 것이 빠르다.

예전에 피라미드같은 문제를 풀었었는데 그때와 풀이가 비슷하다.
밑에서부터 한 칸씩 오르면서 점수를 얻어서 최댓값을 구하는 것이었다.
피라미드는 밑에는 넓지만 위로 갈수록 점점 좁아지며 마지막엔 단 하나만 남는다. 그렇기 때문에 역으로 마지막 지점부터 시작하여 최댓값을 하나씩 누적하여 더해서 값을 구했다.

하지만 이 문제는 순서와 상관없이 해당 번째는 앞, 뒤와 다른 색이어야 한다. 그래서 차례대로 하나 역으로 하나 경우의 수는 똑같이 3가지이므로 순서는 상관없다.

1. r로 시작하는 경우
2. g로 시작하는 경우
3. b로 시작하는 경우

r로 시작했을 경우, 다음 번째는 g와 b 둘 중 작은 것을 선택해야 하고 g와 b도 마찬가지이다.

p[i][0] = min(p[i-1][1], p[i-1][2]) + p[i][0]

현재 해당하는 곳이 r이라면 직전의 집은 반드시 g 혹은 b어야 하고 g와 b를 비교하여 둘 중 작은 쪽과 현재의 비용을 더해서 누적해나간다.

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
for i in range(1,n):
    p[i][0] = min(p[i-1][1], p[i-1][2]) + p[i][0]
    p[i][1] = min(p[i-1][0], p[i-1][2]) + p[i][1]
    p[i][2] = min(p[i-1][0], p[i-1][1]) + p[i][2]
print(min(p[n-1]))