[백준] 1149번 RGB 거리

문제 링크

 

풀이

점화식 d[N]은 N번째 집까지 칠했을 때의 최소 비용으로 정의합니다. 조금 더 정확히 표현하면 N번째 집을 빨간색으로 칠할 때, 초록색으로 칠할 때, 파란색으로 칠할 때의 각 경우의 최소 비용입니다. N-1번째 항에는 이미 N-1번째 집을 빨간색, 초록색, 파란색으로 칠했을 경우의 최소 비용이 이미 구해져 있다는 의미이므로 이전 항의 각 비용 값에 N번째에 칠하고 싶은 색의 비용을 더하면 됩니다. 점화식은 다음과 같습니다.

 

d[N][0] = min(d[N-1][1], d[N-1][2]) + cost[0]

d[N][1] = min(d[N-1][0], d[N-1][2]) + cost[1]

d[N][2] = min(d[N-1][0], d[N-1][1]) + cost[2]

answer = min({d[N][0], d[N][1], d[N][2]})

 

코드

#include <cstdio>
#include <algorithm>
int main()
{
	int N;
	scanf("%d", &N);
	int d[1001][3] = { 0 };
	int cost[3] = { 0 };
	for (int i = 1; i <= N; ++i)
	{
		scanf("%d%d%d", &cost[0], &cost[1], &cost[2]);
		d[i][0] = std::min(d[i - 1][1], d[i - 1][2]) + cost[0];
		d[i][1] = std::min(d[i - 1][0], d[i - 1][2]) + cost[1];
		d[i][2] = std::min(d[i - 1][0], d[i - 1][1]) + cost[2];
	}
	printf("%d\n", std::min({ d[N][0], d[N][1], d[N][2] }));
}