[백준]2096.내려가기

[문제]

www.acmicpc.net/problem/2096

2096번: 내려가기

 

[풀이]

 

DP를 사용해서 이전 경로까지의 최대, 최솟값을 저장해놓고

이전 경로와 현재 위치의 값을 더해서 최대, 최솟값을 구했다.

 

처음에는 N의 범위가 N(1 ≤ N ≤ 100,000)이므로 DP배열을 [100001][3]의 크기고 잡고 시작했는데 메모리 초과가 나왔다.

생각해보니 문제 조건에서 주어진 메모리 제한은 4MB인데 [100001][3]의 크기로 잡고 풀면

min, max 배열이 2개 이므로 4MB를 넘어버린다.

 

생각을 해보니 DP의 값을 계산할 때마다 필요한 값은 현재 위치의 값과 이전 위치의 값이므로

DP 배열의 크기를  [2][3]으로 바꾸고 아래와 같이 풀었다.

 

찾아보니 이러한 기법을 '슬라이딩 윈도우'라고 하는 것 같다.

 

[코드]

 

시간 : 24ms

 

#include <iostream>
#define _max(a,b) ((a) > (b) ? (a) : (b))
#define _min(a,b) ((a) < (b) ? (a) : (b))

using namespace std;

int N;
int map[3];
int DP_max[2][3]={0,};
int DP_min[2][3]={0,};

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

        DP_max[1][0]=map[0] + _max(DP_max[0][0],DP_max[0][1]);
        DP_max[1][1]=map[1] + _max(DP_max[0][0],_max(DP_max[0][1],DP_max[0][2]));
        DP_max[1][2]=map[2] + _max(DP_max[0][1],DP_max[0][2]);
        
        DP_max[0][0]= DP_max[1][0];
        DP_max[0][1]= DP_max[1][1];
        DP_max[0][2]= DP_max[1][2];

        DP_min[1][0]=map[0] + _min(DP_min[0][0],DP_min[0][1]);
        DP_min[1][1]=map[1] + _min(DP_min[0][0],_min(DP_min[0][1],DP_min[0][2]));
        DP_min[1][2]=map[2] + _min(DP_min[0][1],DP_min[0][2]);

        DP_min[0][0]= DP_min[1][0];
        DP_min[0][1]= DP_min[1][1];
        DP_min[0][2]= DP_min[1][2];
    }
    
    cout << _max(DP_max[1][0],_max(DP_max[1][1],DP_max[1][2])) << " "<<_min(DP_min[1][0],_min(DP_min[1][1],DP_min[1][2]));
    
    return 0;
    
}