RGB거리

20 July 2019

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

이번은 i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 풀어보도록 하겠습니다.

#include<stdio.h>


#define MIN(a,b) (((a)<(b))?(a):(b))

static int** color_cost;

int main(void) {

	int N, red, green, blue;

	scanf("%d", &N);

	color_cost = new int*[N];

	for (int i = 0; i < N; i++)
	{
		color_cost[i] = new int[3];
		scanf("%d %d %d", &red, &green, &blue);

		if (i == 0)
		{
			color_cost[i][0] = red;
			color_cost[i][1] = green;
			color_cost[i][2] = blue;
		}
		else {
			color_cost[i][0] = MIN(color_cost[i-1][1], color_cost[i - 1][2]) + red;
			color_cost[i][1] = MIN(color_cost[i - 1][0], color_cost[i - 1][2]) + green;
			color_cost[i][2] = MIN(color_cost[i - 1][1], color_cost[i - 1][0]) + blue;
		}
	}

	int min = color_cost[N-1][0];

	for (int i = 1; i < 3; i++)
	{
		if (color_cost[N-1][i] < min)
		{
			min = color_cost[N - 1][i];
		}
	}

	printf("%d\n", min);

	return 0;
}

먼저 문제의 조건을 보도록 하겠습니다.
R,G,B 중에서 색깔을 칠할 색을 하나 고르고, 그다음에는 중복되는 색을 칠할 수 없습니다.
따라서 R일 경우, 바로 전 값에서 G,B로 결정된 값 중에서 최소의 값,G일 경우, 바로 전 값에서 R,B로 결정한 값 중에서 최소의 값,B일 경우, 바로 전 값에서 R,G로 결정한 값 중에서 최소의 값을 골라주면 됩니다.
전체의 모든 입력을 마치고 마지막 R,G,B 각각의 값에서 가장 작은 값을 출력해주면 됩니다.