RGB ๊ฑฐ๋ฆฌ
๋ฌธ์ ์ ์๋ณธ์ ์ฌ๊ธฐ์ ํ์ธํ์ธ์.
- ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
n๋ฒ์จฐ ์ง์์ ์ ํ๋ ์์ด ์๋ n - 1๋ฒ์งธ ์ง์ ์ต์ ๋์ ํฉ์ ๊ฐ์ง๋ ์์ ๊ฐ์ n๋ฒ์งธ ์ง์์ ์น ํ ์์ ๋น์ฉ์ ๋ํ๋ค.
dp[0][R] = rgb[0][R];
dp[0][G] = rgb[0][G];
dp[0][B] = rgb[0][B];
dp[i][R] = min(dp[i - 1][G], dp[i - 1][B]) + rgb[i][R];
dp[i][G] = min(dp[i - 1][R], dp[i - 1][B]) + rgb[i][G];
dp[i][B] = min(dp[i - 1][R], dp[i - 1][G]) + rgb[i][B];
์์ ์ ํ์์ ์ด์ฉํด n๋ฒ์งธ ๊น์ง ๊ตฌํ๋ค.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
enum Color {
R = 0, G = 1, B = 2
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
int** rgb = new int* [n];
int** dp = new int* [n];
for (int i = 0; i < n; i++) {
rgb[i] = new int[3];
dp[i] = new int[3];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
int cost;
cin >> cost;
rgb[i][j] = cost;
}
}
dp[0][R] = rgb[0][R];
dp[0][G] = rgb[0][G];
dp[0][B] = rgb[0][B];
for (int i = 1; i < n; i++) {
dp[i][R] = min(dp[i - 1][G], dp[i - 1][B]) + rgb[i][R];
dp[i][G] = min(dp[i - 1][R], dp[i - 1][B]) + rgb[i][G];
dp[i][B] = min(dp[i - 1][R], dp[i - 1][G]) + rgb[i][B];
}
int result = dp[n - 1][R];
result = min(result, dp[n - 1][G]);
result = min(result, dp[n - 1][B]);
cout << result << endl;
return 0;
}