[백준 #2096 c++] 내려가기

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

2096번: 내려가기

 

DP문제이다.

처음 접근할 때는 그리디, 완전탐색, DP 중 하나일 것으로 가정한다.

우선 그리디로 해보자.

 

3
1 2 3
4 5 6
4 9 0

 

예제에 나온 숫자대로 탐색할 때

가장 큰 혹은 작은 숫자만 더해서 내려간다고 할 때

 

가장 큰 숫자로는 3 -> 6 -> 9 = 18 (정답) 이지만

가장 작은 숫자로는 1 -> 4 -> 4 = 9 (오답) 으로 실제 정답인 1 -> 5 -> 0 = 6 보다 크기 때문에 그리디로 하기가 까다롭다.

 

그 외에도 여러가지 예외가 발생할 것이기 때문에 그리디로 접근할 수 없다고 볼 수 있다.

 

다음은 완전탐색이다. 이건 생각할 필요도 없이 넘겨야 한다.

왜냐하면 입력으로 받는 줄의 개수가 최대 100,000개 이기 때문에 단순 완전탐색을 하면 3의 100,000 제곱이 되어버리기 때문이다.

 

그렇다는 말은 DP로 밖에 풀 수 없다는 얘기인데, 단순 DP로 접근한다면

9465번 스티커 문제(https://www.acmicpc.net/problem/9465)와 비슷하게 푼다면 쉽게 풀 수 있다.

 

i번째 줄에서 첫 번째 열의 값까지 도달했을 때 최대값은 i - 1 번째 줄에서 첫 번째와 두 번째 열까지의 최대값 중 더 큰 값을 가진다.

두 번째 열인 경우는 첫 번째부터 세 번째 열까지 비교하고,

세 번째 열인 경우는 두 번째와 세 번째 열을 비교한다. 최소값은 더 작은 값을 고르는 형태로 하면 된다.

 

처음에 입력받는 배열을 arr[100'001][3] 이라고 할 때

최대값을 찾는 maxdp[100'001][3] 배열을 만들고 i번째줄의 maxdp 값은 다음처럼 정의할 수 있다.

 

        maxdp[i][0] = max(maxdp[i - 1][0], maxdp[i - 1][1]) + arr[i][0];
        maxdp[i][1] = max(max(maxdp[i - 1][0], maxdp[i - 1][1]), maxdp[i - 1][2]) + arr[i][1];
        maxdp[i][2] = max(maxdp[i - 1][1], maxdp[i - 1][2]) + arr[i][2];

 

하지만 이 문제의 핵심은 메모리이기 때문에 이렇게 막무가내로 배열을 만들어버리면 통과할 수 없다.

우리는 dp가 값을 기록하는 방식을 통해 배열을 전혀 쓰지 않고도 풀 수 있는 방법을 깨달았다.

 

i번째 줄의 dp값은 반드시 i - 1번째 줄의 dp값으로 결정된다. 즉, 직전에 해당하는 값만 알고 있다면 그 이전의 값은 지워져도 무방하다는 말이다.

 

하나의 반복문에서 순차적으로 3개의 값을 입력받음과 동시에 dp에 값을 넣어주는 방식으로 처리할 수 있다는 얘기이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n, tmpa, tmpb, tmpc, maxa, maxb, maxc, mina, minb, minc;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    while (n--) {
        int a, b, c;
        cin >> a >> b >> c;

        tmpa = max(maxa, maxb) + a;
        tmpb = max(max(maxa, maxb), maxc) + b;
        tmpc = max(maxb, maxc) + c;

        maxa = tmpa; maxb = tmpb; maxc = tmpc;

        tmpa = min(mina, minb) + a;
        tmpb = min(min(mina, minb), minc) + b;
        tmpc = min(minb, minc) + c;

        mina = tmpa; minb = tmpb; minc = tmpc;
    }

    cout << max(max(maxa, maxb), maxc) << ' ' << min(min(mina, minb), minc);
    
    return 0;
}