[C++] 백준 1149 : RGB거리

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

1149번: RGB거리

백준 1149번 RGB거리를 풀어봤습니다.

최적해를 구해야 하는데 매 순간 최적해를 구하는 그리디 방법이 아니라 모든 경우를 찾는 동적계획법을 사용했습니다.

마지막 집이 빨강, 초록, 파랑으로 칠해지는 3가지 경우에 대해 dp함수에 넣고, 결과값을 비교해서 최솟값을 출력하면 됩니다.

dp함수에서 이미 계산했던 적이 있는 경우라면 바로 반환합니다.

n==0인 상태에선 입력으로 받았던 color값의 비용을 반환합니다.

위의 두 경우 모두 아니라면 재귀를 통해 최솟값을 찾고 그 값을 배열에 저장한 후 반환합니다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define R 0
#define G 1
#define B 2

int n;
int cost[1000][3];
int homeCost[1000][3];

int dp(int n,int color) {
	if (homeCost[n][color] != 0) {
		return homeCost[n][color];
	}

	if (n == 0) {
		return cost[0][color];
	}

	homeCost[n][color] = min(dp(n - 1,(color + 1) % 3), dp(n - 1, (color + 2) % 3)) + cost[n][color];

	return homeCost[n][color];
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int red, green, blue;
		cin >> red >> green >> blue;
		cost[i][0] = red;
		cost[i][1] = green;
		cost[i][2] = blue;
	}

	int lastHomeR = dp(n - 1, R);
	int lastHomeG = dp(n - 1, G);
	int lastHomeB = dp(n - 1, B);

	if (lastHomeR <= lastHomeG && lastHomeR <= lastHomeB)
		cout << lastHomeR;
	else if (lastHomeG <= lastHomeB)
		cout << lastHomeG;
	else
		cout << lastHomeB;

	return 0;
}