17404 RGB Distance 2

์•Œ๊ณ ๋ฆฌ์ฆ˜ : DP

1. bottom-top ๋ฐฉ์‹์œผ๋กœ ํ’ˆ
2. DP ๊ตฌ์„ฑ : (ํ˜„์žฌ ๊นŠ์ด, ์ด์ „์— ๊ณ ๋ฅธ ์ƒ‰๊น”)์นธ์— ํ˜„์žฌ ๊นŠ์ด์—์„œ์˜ ์ตœ์†Ÿ๊ฐ’ ์ €์žฅ.
3. DP ์ž‘๋™
	a. ์ฒซ๋ฒˆ์งธ ์ง‘์€ for๋ฌธ์œผ๋กœ ํ•˜๋‚˜์”ฉ ๋“ค์–ด๊ฐ.
	b. ๋‘๋ฒˆ์งธ ์ง‘๋ถ€ํ„ฐ ์ด์ „์— ๊ณ ๋ฅธ ์ƒ‰์ด ์•„๋‹Œ ์ƒ‰์œผ๋กœ ์ด๋™
	c. ๋งˆ์ง€๋ง‰์ง‘ + 1์— ๋„์ฐฉํ•˜๋ฉด 0์„ ๋ฆฌํ„ด
	d. ๋งˆ์ง€๋ง‰์ง‘์€ 0๋ฆฌํ„ด ๋ฐ›์€ ๊ฒƒ์— ๊ณ ๋ฅธ ์ƒ‰์˜ ๊ฐ’ ๋”ํ•จ. ์ด ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ์ƒ‰ ๊ฐ’ ์ค‘์˜ ์ตœ์†Ÿ๊ฐ’์„ DP[deep][before]์— ์ €์žฅํ•จ
	e. ํ•˜๋‚˜์”ฉ ์˜ฌ๋ผ๊ฐ€๋ฉด์„œ DP์— ์ €์žฅ
	f. DP์— ์ €์žฅ๋ผ์žˆ๋Š”๊ฒŒ ์žˆ์œผ๋ฉด ๋ฐ”๋กœ ๋ฆฌํ„ด
4. ์ฃผ์˜์ 
	a. ์ฒซ๋ฒˆ์งธ ์ง‘์ด๋ž‘ ๋งˆ์ง€๋ง‰ ์ง‘์ด๋ž‘ ์ƒ‰๊น”์ด ๋‹ฌ๋ผ์•ผํ•จ -> ์ฒซ๋ฒˆ์งธ ์ง‘์˜ ์ƒ‰๊น”์— ๋”ฐ๋ผ์„œ๋„ ์ƒํƒœ๊ฐ€ ๋‹ฌ๋ผ์ง
		-> DP๊ตฌ์„ฑ์„ ์ฒซ๋ฒˆ์งธ ์ง‘์˜ ์ƒํƒœ๊นŒ์ง€ ๊ณ ๋ คํ•˜์—ฌ ํ•ด์•ผํ•จ
		-> ํ•˜์ง€๋งŒ ๋‚˜๋Š” for๋ฌธ์œผ๋กœ ์ฒซ๋ฒˆ์งธ ์ง‘์€ ํ•˜๋‚˜์”ฉ ๋“ค์–ด๊ฐ€๊ณ  ๋‚˜์˜ฌ๋•Œ๋งˆ๋‹ค DP๋ฅผ ์ดˆ๊ธฐํ™” ํ•ด์คฌ๊ธฐ์— ๊ดœ์ฐฎ์Œ
	b. ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ์ƒ‰์˜ ์กฐ๊ฑด๋ฌธ ๊ตฌ์„ฑ์„ ์กฐ์‹ฌํ•ด์•ผํ•จ
		before != 0 && (deep == numOfHouse -1 && first != 0)

		-> ์ด ์กฐ๊ฑด๋ฌธ์€, deep์ด ๋งˆ์ง€๋ง‰์ง‘์ด ์•„๋‹๋•Œ ๋’ท ์กฐ๊ฑด๋ฌธ์—์„œ false๊ฐ€ ๋‚˜์™€ ์ง‘์ด 2๊ฐœ๊ฐ€ ์•„๋‹Œ์ด์ƒ์—์•ผ ์•„์˜ˆ ์ž‘๋™์„ ์•ˆํ•จ.

		๋”ฐ๋ผ์„œ ๋ฐ‘์ฒ˜๋Ÿผ ์งœ์ค˜์•ผํ•œ๋‹ค.
		before != 0 && (deep != numOfHouse -1 || first != 0)
		๋’ท ์กฐ๊ฑด๋ฌธ์€, ๋งˆ์ง€๋ง‰์ด ์•„๋‹ ๊ฒฝ์šฐ true๋ฅผ ๋ฐ˜ํ™˜ํ•˜๊ณ , ๋งˆ์ง€๋ง‰์ง‘์ผ๋•Œ๋Š” first๊ฐ€ 0์ด ์•„๋‹ˆ์—ฌ์•ผ๋งŒ true๊ฐ€ ๋‚˜์˜ด
		-> ์ž˜ ๋งŒ์กฑํ•œ๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#define MAX_HOUSE 1001
#define INFINITE 2000000000
 
using namespace std;
 
int numOfHouse, house[MAX_HOUSE][3], DP[MAX_HOUSE][3], first;
 
int getMinCost(int before, int deep);
int min(int a, int b) {
	return a < b ? a : b;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> numOfHouse;
	for (int i = 0; i < numOfHouse; i++) {
		cin >> house[i][0] >> house[i][1] >> house[i][2];
	}
 
	int minCost = INFINITE;
	for (int i = 0; i < 3; i++) {
		first = i;
		minCost = min(getMinCost(i, 1) + house[0][i], minCost);
		memset(DP, 0, sizeof(DP));
	}
	cout << minCost;
}
 
int getMinCost(int before, int deep) {
	if (deep == numOfHouse) {
		return 0;
	}
	if (DP[deep][before] != 0) {
		return DP[deep][before];
	}
 
 
 
	int a= INFINITE, b = INFINITE, c = INFINITE;
	if (before != 0 && (deep != numOfHouse -1 || first != 0))
		a = getMinCost(0, deep + 1) + house[deep][0];
	if (before != 1 && (deep != numOfHouse - 1 || first != 1))
		b = getMinCost(1, deep + 1) + house[deep][1];
	if (before != 2 && (deep != numOfHouse - 1 || first != 2))
		c = getMinCost(2, deep + 1) + house[deep][2];
 
	int tempMin = min(min(a, b), c);
 
	return DP[deep][before] = tempMin;
}