[Gold V] 내려가기 - 2096

 

[문제 위치]

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

[문제 풀이]

오랜만에 금방 해결한 문제이다.

DP 문제이며 슬라이딩 윈도위의 개념이 포함되어 있다 하는데 슬라이딩 윈도우를 따로 찾아보았지만 DP 문제로만 알아도 될 것 같다.

 

문제를 푸는 방식은 간단했다.

DP를 min을 저장하는 dp와 max를 고르는 dp 두 개를 만들었다.

 

#include <iostream>
#include <vector>
#include <stack>

#define MAX 100001
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int MAP[MAX][3];
int dp_min[MAX][3];
int dp_max[MAX][3];

int main() {
    fastio;
    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> MAP[i][j];
        }
    }
    for (int j = 0; j < 3; j++) {
        dp_max[0][j] = MAP[0][j];
        dp_min[0][j] = MAP[0][j];
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            if (j == 0) {
                dp_min[i][j] = MAP[i][j] + min(dp_min[i - 1][j], dp_min[i - 1][j + 1]);
                dp_max[i][j] = MAP[i][j] + max(dp_max[i - 1][j], dp_max[i - 1][j + 1]);
            } else if (j == 2) {
                dp_min[i][j] = MAP[i][j] + min(dp_min[i - 1][j - 1], dp_min[i - 1][j]);
                dp_max[i][j] = MAP[i][j] + max(dp_max[i - 1][j - 1], dp_max[i - 1][j]);
            } else {
                int tmp_min = min(dp_min[i - 1][j - 1], dp_min[i - 1][j]);
                dp_min[i][j] = MAP[i][j] + min(tmp_min, dp_min[i - 1][j + 1]);

                int tmp_max = max(dp_max[i - 1][j - 1], dp_max[i - 1][j]);
                dp_max[i][j] = MAP[i][j] + max(tmp_max, dp_max[i - 1][j + 1]);
            }
        }
    }

    int ans_max = max(dp_max[N - 1][0], dp_max[N - 1][1]);
    ans_max = max(ans_max, dp_max[N - 1][2]);

    int ans_min = min(dp_min[N - 1][0], dp_min[N - 1][1]);
    ans_min = min(ans_min, dp_min[N - 1][2]);
    
    cout << ans_max << " " << ans_min;
    return 0;
}

이게 가장 처음 작성한 코드이다. 구조에서 보이다 시피 처음 DP 값을 초기화 해준 다음 그 다음 위치부터 bottom-up 방식으로 해결하는 방식이다.

 

각, 자리가 세 자리 뿐이므로 해당 위치까지 도달할 수 있는 최소 혹은 최대 경로를 이전 경로에서 가져와 각 자리에 더하도록 하였다.

 

실행결과 성공적으로 동작하였지만 제출하자 메모리 초과로 실패하게 되었다.

 

이후, 메모를 감소시키기 위해 DP 배열을 다르게 배열하였다.

 

이 문제의 특징은 한 번 방문한 DP의 요소를 재방문할 일이 없다는 것이다. 모든 DP는 최소 혹은 최대 값을 구하기 위해 합산되므로 바로 이전 경로의 DP의 값들만 확인하면 되는 것이다.

 

따라서 N*3크기의 배열 전체를 만들 필요 없이 이전 배열과 현재 배열에 해당하는 1*3 배열 두 개를 만들어 사용하면 되므로 2*3의 메모리만 사용하게 된다.

 

아래는 이를 기반으로 작성한 코드이다.

#include <iostream>
#include <algorithm>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main() {
    fastio;
    int N;
    cin >> N;

    int MAP[3];
    int prev_min[3], prev_max[3], curr_min[3], curr_max[3];

    // 첫 번째 행 입력 및 초기화
    for (int j = 0; j < 3; j++) {
        cin >> MAP[j];
        prev_min[j] = MAP[j];
        prev_max[j] = MAP[j];
    }

    // 나머지 행 처리
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> MAP[j];
        }

        // 현재 행 계산
        curr_min[0] = MAP[0] + min(prev_min[0], prev_min[1]);
        curr_max[0] = MAP[0] + max(prev_max[0], prev_max[1]);

        int temp_min = min(prev_min[0], prev_min[1]);
        curr_min[1] = MAP[1] + min(temp_min, prev_min[2]);

        int temp_max = max(prev_max[0], prev_max[1]);
        curr_max[1] = MAP[1] + max(temp_max, prev_max[2]);

        curr_min[2] = MAP[2] + min(prev_min[1], prev_min[2]);
        curr_max[2] = MAP[2] + max(prev_max[1], prev_max[2]);

        // 현재 행을 이전 행으로 업데이트
        for (int j = 0; j < 3; j++) {
            prev_min[j] = curr_min[j];
            prev_max[j] = curr_max[j];
        }
    }

    int ans_max = max(prev_max[0], prev_max[1]);
    ans_max = max(ans_max, prev_max[2]);

    int ans_min = min(prev_min[0], prev_min[1]);
    ans_min = min(ans_min, prev_min[2]);

    cout << ans_max << " " << ans_min;
    return 0;
}