[python] 1149, RGB 거리 : 다이나믹 프로그래밍

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번 집의 색과 같지 않아야 한다.

 

[입력]

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

 

[출력]

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

 

[예제]

 

[풀이]

💡 문제 요약 : 모든 집을 칠하는 비용의 최솟값

💡 풀이 포인트

 DP를 사용하여 각 상황에서의 최소값을 다음에도 사용한다. DP를 풀면서 느끼는 DP의 특징은 현재의 값에 집중한다는 점인 것 같다. 현재에 R, G, B를 각각 선택했을 때의 최소값을 구하는 것이 해당 문제의 포인트이다.

 현재에 R을 선택하기 위해서는 이전의 선택이 G, B 였어야 하기 때문에 이전 G, B 중 값이 더 적은 것을 선택하여 현재의 R과 더해준다. 이러한 방식을 G, B에도 함께 적용해준다면 풀 수 있는 문제였다. 

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

dp = [[0, 0, 0] for _ in range(n)] 
dp[0][0], dp[0][1], dp[0][2] = rgb_lst[0][0], rgb_lst[0][1], rgb_lst[0][2] 

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

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