Skip to content

Latest commit

ย 

History

History
80 lines (58 loc) ยท 1.63 KB

File metadata and controls

80 lines (58 loc) ยท 1.63 KB

๋ฌธ์ œ

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