백준알고리즘 1149번. RGB거리 풀이

최근에 익힌 동적분할 메모이제이션으로 2번만에 성공했습니다 :)

최대 1000개의 직선으로 늘어선 건물을 빨강, 녹색, 파랑색으로 칠하면서 각 건물당 드는 비용을 최소화하는 경로를 찾는 문제인데요. 각 이어진 건물은 같은 색으로 칠해서는 안되는 제약이 있습니다.

​

문제링크

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

​

크레이는 동적분할로 풀었습니다.

소스 설명보다는 그냥 원리 설명을 드릴텐데요.

간편화를 위해 빨강은 R, 녹색은 G, 파랑은 B로 표현해보도록 하겠습니다.

​

1번째 색상을 R로 칠하고, 2번째 이후에는 G, B 로 칠하기 시작하는 경로중 작은 값을 구합니다.

1번째 색상을 G로 칠하고, 2번째 이후에는 R, B 로 칠하기 시작하는 경로중 작은 값을 구합니다.

1번째 색상을 B로 칠하고, 2번째 이후에는 R, G 로 칠하기 시작하는 경로중 작은 값을 구합니다.

​

2번쨰 이후 각 색으로 칠하는 경로중 작은 값은 또 이렇게 구합니다.

​

2번째 색상을 R로 칠하고, 3번째 이후에는 G, B 로 칠하기 시작하는 경로중 작은 값을 구합니다.

2번째 색상을 G로 칠하고, 3번째 이후에는 R, B 로 칠하기 시작하는 경로중 작은 값을 구합니다.

2번째 색상을 B로 칠하고, 3번째 이후에는 R, G 로 칠하기 시작하는 경로중 작은 값을 구합니다.

​

3번째부터 999번째까지 똑같은 전철을 밟아가면 1~1000단계까지 가장 적은 비용을 산출할 수 있습니다.

​

단, 이 방법만을 그대로 사용하면, 엄청난 기하급수적인 반복적인 계산이 이루어지기 때문에

한가지 기법이 더 들어가는 것이지요.

예를들면 500번째 이후 R, G, B 로 각각 칠하는 가장 적은 비용을 한번 기억해 놓으면

다음번에는 그 계산을 할 필요가 없는 것입니다.

발생하는 모든 상황에 대해 그 경우의 값을 저장해놓는 것이지요.

단계마다 R,G,B 각각 3가지 경우가 있어 1000개의 집을 색칠한다고 치면 3000개의 저장할 공간을 마련하면 되는데 아래 소스에서는 sum[1001][3] 이 그 용도로 사용됩니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <list>
#include <cmath>
using namespace std;

int n;
int cost[1001][3];	// RGB 금액
long long sum[1001][3];

long long lowcost(int p, int color)
{
	if(p==n) return cost[p][color];

	long long thiscost = cost[p][color];
	p++;
	long long costR;
	if(sum[p][0]==-1)sum[p][0]=lowcost(p, 0);
	costR=sum[p][0];

	long long costG;
	if(sum[p][1]==-1)sum[p][1]=lowcost(p, 1);
	costG=sum[p][1];

	long long costB;
	if(sum[p][2]==-1)sum[p][2]=lowcost(p, 2);
	costB=sum[p][2];

	if(color==0)
	{
		if(costG<costB)return costG + thiscost;
		else return costB + thiscost;
	}
	if(color==1)
	{
		if(costR<costB)return costR + thiscost;
		else return costB + thiscost;
	}
	if(costR<costG)return costR + thiscost;
	return costG + thiscost;
}

void Result()
{
	scanf("%d", &n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d %d %d",
			&cost[i][0],		// R비용
			&cost[i][1],		// G비용
			&cost[i][2]);		// B비용
	}

	for(int i=1;i<=n;++i)
	{
		sum[i][0]=sum[i][1]=sum[i][2]=-1;
	}

	long long sumR = lowcost(1, 0);	// R
	long long sumG = lowcost(1, 1);	// G
	long long sumB = lowcost(1, 2);	// B
	long long sumFinal;
	if(sumR <= sumG && sumR <= sumB ) sumFinal= sumR;
	if(sumG <= sumR && sumG <= sumB ) sumFinal= sumG;
	if(sumB <= sumR && sumB <= sumG ) sumFinal= sumB;

	printf("%lld", sumFinal);
	
}

int main()
{
	Result();
	return 0;
}