Baekjoon 2096번 내려가기

문제

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

걸린 시간

-

풀이

C++

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

#define INF 987654321

int N;
int arr[100000][3];
int c1[2][3]; // max
int c2[2][3]; // min

// 반복적인 dp 풀이 : Bottom-Up
int iterative1(){
    // 기저 사례 : N 층의 값 초기화
    for(int x = 0; x < 3; x++)
        c1[(N-1)%2][x] = arr[(N-1)][x]; 

    for(int y = N-2; y >= 0; y--){
        for(int x = 0; x < 3; x++){
            if(x == 0)
                c1[y%2][x] = max({c1[(y+1)%2][x], c1[(y+1)%2][x+1]}) + arr[y][x];
            else if(x == 1)
                c1[y%2][x] = max({c1[(y+1)%2][x-1], c1[(y+1)%2][x], c1[(y+1)%2][x+1]}) + arr[y][x];
            else
                c1[y%2][x] = max({c1[(y+1)%2][x-1], c1[(y+1)%2][x]}) + arr[y][x];
        }
    }

    return max({c1[0][0], c1[0][1], c1[0][2]});
}

int iterative2(){
    // 기저 사례 : N 층의 값 초기화
    for(int x = 0; x < 3; x++)
        c2[(N-1)%2][x] = arr[(N-1)][x]; 

    for(int y = N-2; y >= 0; y--){
        for(int x = 0; x < 3; x++){
            if(x == 0)
                c2[y%2][x] = min({c2[(y+1)%2][x], c2[(y+1)%2][x+1]}) + arr[y][x];
            else if(x == 1)
                c2[y%2][x] = min({c2[(y+1)%2][x-1], c2[(y+1)%2][x], c2[(y+1)%2][x+1]}) + arr[y][x];
            else
                c2[y%2][x] = min({c2[(y+1)%2][x-1], c2[(y+1)%2][x]}) + arr[y][x];
        }
    }

    return min({c2[0][0], c2[0][1], c2[0][2]});
}

int main(){
    scanf("%d", &N);
    memset(arr, -1, sizeof(arr));

    for(int i = 0; i < N; i++)
        scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]); 

    printf("%d %d\n", iterative1(), iterative2());

    return 0;
}

재귀적 동적 계획법은 30만 크기의 int 형 배열이 3개가 필요하다. 300,000 * 4 * 3 = 3,600,000 byte 로 메모리 제한 4mb 를 통과할 것 같지만 사용환경에 따라서 sizeof(int) 의 크기는 달라질 수 있기 때문에 메모이제이션 대신 다른 방법을 사용해야한다.

재귀적인 구조(Top-Down)를 반복적(Bottom-Up)으로 변경하면 부분 문제가 계산되는 순서들이 일정하게 되어 슬라이딩 윈도우 기법을 사용할 수 있다. 이는 과거에 계산한 값을 모두 저장하는 메모이제이션과 달리 이전의 정보만 저장하기 때문에 메모리가 훨씬 절약된다.