[C++][백준] 2096 내려가기

문제
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

 

출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

 

어떻게 풀어야 할까?

처음에는 일반 DP처럼 다 입력을 받고, 순차적으로 큰것들로 아래 배열의 값들을 업데이트 하는 방식으로 풀어보려고 시도하였다.

그러나, 메모리 제한이 4MB이기 때문에 3*N 배열 2개를 선언하고 그 값을 갱신해 나가는 방법을 사용하게 되면 메모리 초과가 발생하게 되는 문제를 발견하였다.

메모리 문제를 줄이기 위해 좀 더 고민해본 결과, 계산할 때 필요한 것은 현재 계산해야 하는 열, 이전 열 2개 뿐이다. 그러나 3*2 배열을 만들고 계속 스왑하고 더하기에는 시간이 오래 걸릴 거 같기 때문에 3칸짜리 배열 3개(최대, 최소, 입력), 이전 값을 저장할 temp변수 6개로 계산을 진행하였다.

 

코드를 살펴보자

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N,temp1,temp2,temp3,temp4,temp5,temp6;

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

    cin >> N;
    vector<ll> Max(3);
    vector<ll> Min(3);
    vector<ll> input(3);
    for (ll i = 0; i < 3; i++) {
        cin >> Max[i];
        Min[i] = Max[i];
    }
    for (int i=0; i<N-1; i++) {
        cin >> input[0] >> input[1] >> input[2];
        temp1 = Max[0]; temp2 = Max[1], temp3 = Max[2], temp4 = Min[0], temp5 = Min[1], temp6 = Min[2];
        Max[0] = max(temp1, temp2) + input[0];
        Max[2] = max(temp2,temp3) + input[2];
        Max[1] = max(max(temp1,temp2),temp3) + input[1];
        Min[0] = min(temp4, temp5) + input[0];
        Min[2] = min(temp5,temp6) + input[2];
        Min[1] = min(min(temp4,temp5),temp6) + input[1];
    }
    cout << max(max(Max[0],Max[1]),Max[2]) << ' ' << min(min(Min[0],Min[1]),Min[2]);

    return 0;
}

 

이런식으로 이전 값들 중 최대/최소 값으로 다음 값을 업데이트 해주면 풀 수 있는 문제였다.