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;
}