2096번-내려가기

문제

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

2096번: 내려가기

---

접근방법

1) 접근 사고

모두 입력받아서 갱신할 필요없이 값을 입력받은 뒤에 받은 순간마다 판단해주면 되는 문제입니다.

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
int maxDP[3];
int minDP[3];
int input[3];
int tmp0, tmp2;
 
int main(void)
{
    fastio;
 
    int n;
    cin >> n;
    cin >> maxDP[0] >> maxDP[1] >> maxDP[2];
    minDP[0] = maxDP[0];
    minDP[1] = maxDP[1];
    minDP[2] = maxDP[2];
 
    for(int i = 1; i < n; i++)
    {
        cin >> input[0] >> input[1] >> input[2];
        tmp0 = maxDP[0];
        tmp2 = maxDP[2];
        maxDP[0] = max(maxDP[0], maxDP[1]) + input[0];
        maxDP[2] = max(maxDP[1], maxDP[2]) + input[2];
        maxDP[1] = max({tmp0,tmp2,maxDP[1]}) + input[1];
 
        tmp0 = minDP[0];
        tmp2 = minDP[2];
        minDP[0] = min(minDP[0],minDP[1]) + input[0];
        minDP[2] = min(minDP[1], minDP[2]) + input[2];
        minDP[1] = min({tmp0,tmp2,minDP[1]}) + input[1];
    }
    cout << max({maxDP[0], maxDP[1], maxDP[2]}) << " ";
    cout << min({minDP[0], minDP[1], minDP[2]});
}