BOJ 2096: 내려가기 [C++]

문제

2096번: 내려가기

 

 

처음 문제를 봤을 때는 DP를 생각했는데, 메모리 제한이 4MB라 'DP쓰면 메모리 넘칠거 같은데?'라고 생각해서

완탐을 썼다.

 

결과는 당연히 시간 초과.

 

그래서 DP로 풀어보는데,

처음에는 들어올 수 있는 모든 수를 담을 수 있도록 배열을 선언했다.

int nums[100000][3];
int dp[100000][3][2];

 

역시 메모리 초과.

 

 

글 읽기 - 메모리 초과가 납니다... 고수님들 도와주세요 ㅠㅠㅠ

이 글을 보고 '아 그럼 숫자 받는 배열은 다 잡을 필요가 없겠네' 하고 이렇게 바꿨다.

int nums[3];
int dp[100000][3][2];

 

근데도 시간 초과.

 

'???'

 

'아 그럼 dp 배열도 2개만 만들어서 하나는 이전, 하나는 지금 순서의 값을 채우는 용으로 쓰면 되겠네'라고 생각해서

이렇게 바꾸어 통과했다.

 

#include <iostream>

int dp[2][3][2];
int nums[3];

int main() {
    int n = 0;
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            std::cin >> nums[j];
        }
        if (i == 0) {
            for (int j = 0; j < 3; j++) {
                dp[0][j][0] = nums[j];
                dp[0][j][1] = nums[j];
                dp[1][j][0] = 900001;
                dp[1][j][1] = 0;
            }
            continue;
        }
        for (int j = 0; j < 3; j++) {
            if (j - 1 >= 0) {
                // minimum
                if (dp[0][j - 1][0] + nums[j] < dp[1][j][0]) {
                    dp[1][j][0] = dp[0][j - 1][0] + nums[j];
                }
                // maximum
                if (dp[0][j - 1][1] + nums[j] > dp[1][j][1]) {
                    dp[1][j][1] = dp[0][j - 1][1] + nums[j];
                }
            }
            // minimum
            if (dp[0][j][0] + nums[j] < dp[1][j][0]) {
                dp[1][j][0] = dp[0][j][0] + nums[j];
            }
            // maximum
            if (dp[0][j][1] + nums[j] > dp[1][j][1]) {
                dp[1][j][1] = dp[0][j][1] + nums[j];
            }
            if (j + 1 < 3) {
                // minimum
                if (dp[0][j + 1][0] + nums[j] < dp[1][j][0]) {
                    dp[1][j][0] = dp[0][j + 1][0] + nums[j];
                }
                // maximum
                if (dp[0][j + 1][1] + nums[j] > dp[1][j][1]) {
                    dp[1][j][1] = dp[0][j + 1][1] + nums[j];
                }
            }
        }
        for (int j = 0; j < 3; j++) {
            dp[0][j][0] = dp[1][j][0];
            dp[0][j][1] = dp[1][j][1];
            dp[1][j][0] = 900001;
            dp[1][j][1] = 0;
        }
    }

    int max_sum = 0;
    int min_sum = 900001;
    for (int i = 0; i < 3; i++) {
        if (dp[0][i][0] < min_sum) {
            min_sum = dp[0][i][0];
        }
        if (dp[0][i][1] > max_sum) {
            max_sum = dp[0][i][1];
        }
    }

    std::cout << max_sum << " " << min_sum << "\n";

    return 0;
}

 

그런데 이렇게 하고도 별로인 것 같아서 구글링 해보니,

dp 배열도 저만큼 잡을 필요가 없었다.

 

#include <iostream>

int dp[3][2];
int nums[3];
int left_tmp;
int right_tmp;

int main() {
    int n = 0;
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            std::cin >> nums[j];
            if (i == 0) {
                dp[j][0] = nums[j];
                dp[j][1] = nums[j];
            }
        }
        if (i == 0) {
            continue;
        }
        // minimum
        left_tmp = dp[0][0];
        right_tmp = dp[2][0];
        dp[0][0] = std::min(dp[0][0], dp[1][0]) + nums[0];
        dp[2][0] = std::min(dp[1][0], dp[2][0]) + nums[2];
        dp[1][0] = std::min(std::min(left_tmp, dp[1][0]), right_tmp) + nums[1];

        // maximum
        left_tmp = dp[0][1];
        right_tmp = dp[2][1];
        dp[0][1] = std::max(dp[0][1], dp[1][1]) + nums[0];
        dp[2][1] = std::max(dp[1][1], dp[2][1]) + nums[2];
        dp[1][1] = std::max(std::max(left_tmp, dp[1][1]), right_tmp) + nums[1];
    }

    std::cout << std::max(std::max(dp[0][1], dp[1][1]), dp[2][1]) << " " << std::min(std::min(dp[0][0], dp[1][0]), dp[2][0]) << "\n";

    return 0;
}