백준 2096번 : 내려가기

  만약 평범한 DP 문제였다면 그렇게 어렵지 않았을 것이다. 하지만 이 문제가 골드 4인 이유는 메모리 제한 때문이겠지! 그래서 원래라면 100000 * 3 짜리 2차원 array를 3개 정도 만들어서 기록하면서 진행했겠지만 그렇게하면 메모리 초과가 발생하기 때문에 한 줄 입력을 받을 때마다 바로 계산하는 방식으로 했다. 계산 자체는 그렇게 어렵지 않다. 문제에서 설명하는 그대로 max함수와 min함수를 이용해서 계산하면 된다.

#include <stdio.h>
#include <iostream>
 
using namespace std;

int n;
int map[3], maxCnt[3], minCnt[3];

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        cin >> map[0] >> map[1] >> map[2];
        
        if(i == 0)
        {
            maxCnt[0] = map[0];
            maxCnt[1] = map[1];
            maxCnt[2] = map[2];
            minCnt[0] = map[0];
            minCnt[1] = map[1];
            minCnt[2] = map[2];
        }
        else
        {
            int preMaxCnt[3] = { maxCnt[0], maxCnt[1], maxCnt[2] };
            maxCnt[0] = max(preMaxCnt[0], preMaxCnt[1]) + map[0];
            maxCnt[1] = max(max(preMaxCnt[0], preMaxCnt[1]), preMaxCnt[2]) + map[1];
            maxCnt[2] = max(preMaxCnt[1], preMaxCnt[2]) + map[2];
            
            int preMinCnt[3] = { minCnt[0], minCnt[1], minCnt[2] };
            minCnt[0] = min(preMinCnt[0], preMinCnt[1]) + map[0];
            minCnt[1] = min(min(preMinCnt[0], preMinCnt[1]), preMinCnt[2]) + map[1];
            minCnt[2] = min(preMinCnt[1], preMinCnt[2]) + map[2];
        }
    }
    
    cout << max(max(maxCnt[0], maxCnt[1]), maxCnt[2]) << " " << min(min(minCnt[0], minCnt[1]), minCnt[2]);
 
    return 0;
}