dp 백준 1149번 RGB거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

RGB 거리는 각각의 모든 집들의 비용을 최소로 만들면서 서로 겹치지 않게 만드는 문제이다. 위 문제는 결론적으로 

현재의 경우가 이전의 같은 색을 제외하고 다른 두가지 색을 선택한다는 조건이 있다. 현재와 다른 이전 두 색 을 고르면서 최소의 값으로 만드는 점에 집중하면 된다. 

price[2][0] = min(price[1][1], price[1][2]) + home[2][0];
price[2][1] = min(price[1][0], price[1][2]) + home[2][1];
price[2][2] = min(price[1][0], price[1][1]) + home[2][2];

위와 같이 점화식을 세워면 저도 처음에는 생각이 안나 다른 사람의 풀이를 참고하여 해결했습니다. 이럴 때 마다 제 자신의 부끄럽습니다. 왜 이렇게 멍청하나 자책감도 들구요 그래서 완벽히 내껄로 만들려고합니다. 할튼

 

세 경우의 최종 가격은 3개여야 하기 때문에 각 부분 당 이전 단계 두 부분 중 큰 값을 선택하여 그 단계의 돈과 더해주면 됩니다. 결국 아래와 같은 점화식이 완성됩니다. 

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + arr[i][2];

#include <cstdio>
#include <algorithm>
using namespace std;

int N;
int arr[1002][3];
int dp[1002][3];

int main(){
	scanf("%d", &N);

	for(int i = 0; i < N; i++)
		scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]);

	dp[0][0] = arr[0][0];
	dp[0][1] = arr[0][1];
	dp[0][2] = arr[0][2];

	for(int i = 1; i < N; i++){
		dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
		dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
		dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + arr[i][2];
	}

	printf("%d", *min_element(dp[N-1], dp[N-1]+3));
}