BaekJoon 1149 RGB 거리

Link https://www.acmicpc.net/problem/1149
소스결과 2012 KB / 0 ms

출처 Backjoon 

언어 C++ 17

분류 다이나믹프로그래밍

 

설명

이웃한 집과 같은색으로 칠하지 않으면서 모든 집을 칠할 때 드는 비용의 최솟값을 출력하는 문제

 

이전 집의 색을 기억해서 같은 색이면 그 색을 제외하고 최솟값을 구해 마지막까지 칠하는 경우

모든 경우에서 최솟값을 선택하는 그리디 알고리즘을 적용시키면 문제의 정답이 나오지는 않는다.

 

같은 값이 존재하는 경우 위치에 따라 다른 결과 값이 나올 수 있다는 점을 유의해야한다.

또한 매번 최선의 선택이 정답이 되지 않기 때문에 모든 경우에 대해서 검사를 해야 한다.

 

DFS로 풀어나가면 시간 초과가 나온다.

 

점화식은

첫 번쨰 경우를 제외하고 이전 집의 색과 다른 집에서의 합이 최소가 되는 경우를 저장하는 점화식을 가진다.

dpTable[i][j] = RGB_val[i][j] + min(dpTable[i - 1][(j + 1) % 3], dpTable[i - 1][(j + 2) % 3]); ( 단 i > 0 )

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000;

int tcc;
int RGB_val[MAX + 1][3];
int dpTable[MAX + 1][3];

int myMin(int val1, int val2)
{
	return val1 > val2 ? val2 : val1;
}

int main()
{
	cin >> tcc;

	for (int i = 0; i < tcc; i++)
		for (int j = 0; j < 3; j++)
			cin >> RGB_val[i][j];

	for (int i = 0; i < 3; i++)
		dpTable[0][i] = RGB_val[0][i];

	for (int i = 1; i < tcc; i++)
	{
		for (int j = 0; j < 3; j++)
			dpTable[i][j] = RGB_val[i][j] + myMin(dpTable[i - 1][(j + 1) % 3], dpTable[i - 1][(j + 2) % 3]);

	}

	int minVal = dpTable[tcc-1][0];
	for (int i = 1; i < 3; i++)
		if (minVal > dpTable[tcc - 1][i])
			minVal = dpTable[tcc - 1][i];

	cout << minVal;
	return 0;
}