Notice
Recent Posts
Recent Comments
Link
«   2024/09   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Tags more
Archives
Today
Total
관리 메뉴

fatalite

내려가기 - 백준 2096번 본문

카테고리 없음

내려가기 - 백준 2096번

fataliteforu 2023. 7. 31. 07:40

Problem

Dynamic Programming, 골드 5

 

Solution

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <queue>


using namespace std;



int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int Number;
    cin >> Number;

    vector<int> Table(3);
    vector<vector<int>> DPMaxMemory(2,vector<int>(3));
    vector<vector<int>> DPMinMemory(2, vector<int>(3));
    for (int i = 0; i < Number; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        Table[0] = a;
        Table[1] = b;
        Table[2] = c;

        if (i == 0) {
            DPMaxMemory[0][0] = a;
            DPMaxMemory[0][1] = b;
            DPMaxMemory[0][2] = c;

            DPMinMemory[0][0] = a;
            DPMinMemory[0][1] = b;
            DPMinMemory[0][2] = c;

        }
        else {
            DPMaxMemory[1][0] = max(DPMaxMemory[0][0], DPMaxMemory[0][1]) + Table[0];

            DPMaxMemory[1][1] = max(
                max(DPMaxMemory[0][1], DPMaxMemory[0][2]),DPMaxMemory[0][0]) + Table[1];

            DPMaxMemory[1][2] = max(DPMaxMemory[0][1], DPMaxMemory[0][2]) + Table[2];

            DPMaxMemory[0][0] = DPMaxMemory[1][0];
            DPMaxMemory[0][1] = DPMaxMemory[1][1];
            DPMaxMemory[0][2] = DPMaxMemory[1][2];

            DPMinMemory[1][0] = min(DPMinMemory[0][0], DPMinMemory[0][1]) + Table[0];

            DPMinMemory[1][1] = min(
                min(DPMinMemory[0][1], DPMinMemory[0][2]), DPMinMemory[0][0]) + Table[1];

            DPMinMemory[1][2] = min(DPMinMemory[0][1], DPMinMemory[0][2]) + Table[2];

            DPMinMemory[0][0] = DPMinMemory[1][0];
            DPMinMemory[0][1] = DPMinMemory[1][1];
            DPMinMemory[0][2] = DPMinMemory[1][2];


        }

    }
    cout << max(max(DPMaxMemory[0][0], DPMaxMemory[0][1]), DPMaxMemory[0][2]) << " "
        << min(min(DPMinMemory[0][0], DPMinMemory[0][1]), DPMinMemory[0][2]);
}