백준 2096 내려가기

골드 5 난이도의 dp문제이다.

 

문제를 처음 읽으면 굉장히 간단한 dp문제로 보인다.

 

 

max_dp[i][j] => i행 j열까지 내려왔을 때, 점수들의 합이 가장 큰 값
min_dp[i][j] => i행 j열까지 내려왔을 때, 점수들의 합이 가장 작은 값

 

 

1. 하지만 메모리 제한이 4MB이기 때문에, max_dp와 min_dp를 넉넉하게 최대값인 100001 * 4로 잡는 순간

 

메모리 초과가 뜨게 된다.

 

그래서 조금 더 생각을 해 보면, 딱 2개의 row만 필요함을 알 수 있다.

 

첫 row는 현재 행 까지의 최대(최소)값 들을,

다음 row는 해당 행 까지의 최대(최소)값을 넣어주고

 

다음 행을 조사하기 직전에, 마지막 row의 모든 값들을 첫 row로 이동 해 주면 되는 것이다.

 

따라서, 2 * 3 배열로도 충분히 풀 수 있는 문제이다.

 

 

 

2. 또한, n이 1인 경우에도 처리를 해 주어야 한다.

 

따라서 처음 map을 입력 받을 때, max_dp와 min_dp의 첫 행을 map의 첫 행의 값들과 동일하도록 초기화 해 주면 된다.

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

int map[100001][3];
int max_dp[2][3];
int min_dp[2][3];
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++){
            cin >> map[i][j];
            if(i == 1){
                max_dp[i][j] = min_dp[i][j] = map[i][j];
            }
            if(i == 2) {
                min_dp[i-1][j] = INT_MAX;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++){
            if(j==0){
                max_dp[1][j] = max(max_dp[0][j] + map[i][j], max_dp[1][j]);
                max_dp[1][j+1] = max(max_dp[0][j] + map[i][j+1], max_dp[1][j+1]);
                min_dp[1][j] = min(min_dp[0][j] + map[i][j], min_dp[1][j]);
                min_dp[1][j+1] = min(min_dp[0][j] + map[i][j+1], min_dp[1][j+1]);
            }
            else if(j == 2){
                max_dp[1][j-1] = max(max_dp[0][j] + map[i][j-1], max_dp[1][j-1]);
                max_dp[1][j] = max(max_dp[0][j] + map[i][j], max_dp[1][j]);
                min_dp[1][j-1] = min(min_dp[0][j] + map[i][j-1], min_dp[1][j-1]);
                min_dp[1][j] = min(min_dp[0][j] + map[i][j], min_dp[1][j]);
            } else {
                max_dp[1][j] = max(max_dp[0][j] + map[i][j], max_dp[1][j]);
                max_dp[1][j+1] = max(max_dp[0][j] + map[i][j+1], max_dp[1][j+1]);
                max_dp[1][j-1] = max(max_dp[0][j] + map[i][j-1], max_dp[1][j-1]);
                min_dp[1][j] = min(min_dp[0][j] + map[i][j], min_dp[1][j]);
                min_dp[1][j+1] = min(min_dp[0][j] + map[i][j+1], min_dp[1][j+1]);
                min_dp[1][j-1] = min(min_dp[0][j] + map[i][j-1], min_dp[1][j-1]);
            }
        }
        for(int j = 0; j < 3; j++){
            max_dp[0][j] = max_dp[1][j];
            max_dp[1][j] = 0;
            min_dp[0][j] = min_dp[1][j];
            min_dp[1][j] = INT_MAX;
        }
    }
    int max_answer = 0; int min_answer = INT_MAX;
    for(int i = 0; i < 3; i++){
        max_answer = max(max_answer, max_dp[0][i]);
        min_answer = min(min_answer, min_dp[0][i]);
    }
    cout << max_answer << ' ' << min_answer;
    return 0;
}