1149 RGB ๊ฑฐ๋ฆฌ

์•Œ๊ณ ๋ฆฌ์ฆ˜(dp)

1. ๊ทธ๋ƒฅ ํ˜„์žฌ ๋…ธ๋“œ์—์„œ ์ด์ „์˜ ์ƒํƒœ๊ฐ€ X์˜€์„๋•Œ์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ €์žฅํ•˜๋Š” dp ๋ฐฐ์—ด DP[1000][3] ์„ ์„ ์–ธํ•˜๊ณ  DP๋ฅผ ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.
2. ์ฒซ๋ฒˆ์งธ์™€ ๋งˆ์ง€๋ง‰์ด ์ƒ๊ด€์ด์—†์œผ๋ฏ€๋กœ ๋งค๋ฒˆ ๊ฐ’์„ ์ดˆ๊ธฐํ™” ์‹œ์ผœ์ค„ ํ•„์š”๋Š” ์—†๋‹ค.

์ฝ”๋“œ

#include <iostream>
#define INF 2000000000
using namespace std;
 
int N, cost[1000][3], DP[1000][3];
 
int getMin(int deep, int bf);
int min(int a, int b) {
	return a < b ? a : b;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
 
	int result = INF;
	for (int i = 0; i < 3; i++) {
		result = min(result, getMin(1, i) + cost[0][i]);
	}
 
	cout << result;
}
 
int getMin(int deep, int bf) {
	if (deep == N) {
		return 0;
	}
	if (DP[deep][bf] != 0)
		return DP[deep][bf];
 
	int result = INF;
 
	for (int i = 0; i < 3; i++)
		if (i != bf)
			result = min(result, getMin(deep + 1, i)+ cost[deep][i]);
 
	return DP[deep][bf] = result;
}