[백준][dp] 2096 내려가기 C++구현

목차

https://www.acmicpc.net/problem/2096

문제

 

문제 구현 방향

NodeJs로 dp구현하다가 메모리 초과를 해결할 수 없어서 c++로 다시 만들었다.

4mb제한이니 일차원 배열에 계속 초기화하는 식으로 누적했다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>

using namespace std;

int N;
int board[100001][3] = {0};
vector<int> dp;
vector<int> save;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> board[i][j];
        }
    }
    for (int i = 0; i < 3; i++) {
        dp.push_back(board[0][i]);
    }
    for (int i = 1; i < N; i++) {
        save.push_back(board[i][0] + max(dp[0], dp[1]));
        save.push_back(board[i][1] + max({ dp[0], dp[1], dp[2] }));
        save.push_back(board[i][2] + max(dp[1], dp[2]));
        dp[0] = save[0];
        dp[1] = save[1];
        dp[2] = save[2];
        save.clear();
    }
    int m = max({ dp[0], dp[1], dp[2] });
    dp.clear();
    for (int i = 0; i < 3; i++) {
        dp.push_back(board[0][i]);
    }
    for (int i = 1; i < N; i++) {
        save.push_back(board[i][0] + min(dp[0], dp[1]));
        save.push_back(board[i][1] + min({ dp[0], dp[1], dp[2] }));
        save.push_back(board[i][2] + min(dp[1], dp[2]));
        dp[0] = save[0];
        dp[1] = save[1];
        dp[2] = save[2];
        save.clear();
    }
    int n = min({ dp[0], dp[1], dp[2] });
    cout << m << " " << n;
    return 0;
}