🔗 문제

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

✏️ 풀이

이 문제가 원하는 답은 2개다. 게임 결과의 최대, 최소이다.

어떻게 하면 최대를 구할 수 있을까?
어떻게 하면 최소를 구할 수 있을까?

결론적으로, 최대값과 최소값을 구하는 점화식은 거의 동일합니다. 각 선택지마다 갈 수 있는 경로가 정해져 있기 때문에, 바로 직전의 위치만 비교하면 됩니다. 이렇게 최대값(max_dp)과 최소값(min_dp)을 갱신해 나가면 됩니다. (코드는 아래를 참고하세요.)

for(int i=0; i<N; ++i)
{
    max_dp[i+1][0] = std::max(max_dp[i][0], max_dp[i][1]) + arr[i+1][0];
    min_dp[i+1][0] = std::min(min_dp[i][0], min_dp[i][1]) +  arr[i+1][0];

    max_dp[i+1][1] = std::max(std::max(max_dp[i][0], max_dp][1]), max_dp[i][2]) + arr[i+1][1];
    min_dp[i+1][1] = std::min(std::min(min_dp[i][0], min_dp[i][1]), min_dp[i][2]) + arr[i+1][1];

    max_dp[i+1][2] = std::max(max_dp[i][1], max_dp[i][2]) + arr[i+1][2];
    min_dp[i+1][2] = std::min(min_dp[i][1], min_dp[i][2]) + arr[i+1][2];
}

메모리 제한

이 문제는 단순히 점화식을 짜는 것이지만, 골드 문제인 이유는 메모리 조건에 있습니다. 메모리 제한이 4MB입니다. 4MB면 대략적으로 int는 100만 개 이하로 선언할 수 있습니다. 하지만 메인 함수가 얼마나 메모리를 사용할지 모르니, 안전하게 50만 개로 잡는게 좋겠다.. 생각만 하고 시작했습니다.

문제에서 N은 최대 10만 개입니다. 기존 입력은 3 * 10만 개로 30만 개, DP를 작성하기 위한 최대, 최소 배열은 각각 30만 개씩 필요합니다. 총 90만 개의 배열을 선언하게 되면???????????????????????? 메모리 초과가 발생합니다.

기존 입력 3*10만개 → 30만개
DP를 작성하기 위한 최대, 최소 배열 → 30만개, 30만개
총 : 90만개

해결 방법

점화식을 다시 살펴보면, 순서대로 나아가면서 계산이 완료되면 이전 값은 더 이상 사용하지 않습니다. 입력값은 현재 값만 사용하므로 3개, DP 또한 바로 직전의 값과 현재의 값만 필요하므로 각각 2 * 3개씩 필요합니다. 총 15개의 메모리만 필요합니다.

정말 조금만 더 생각해보면, 총 90만 개에서 15개로 메모리를 줄일 수 있습니다.

또한, 최대값을 구한 후 배열을 재활용하여 최소값을 구하면 메모리를 더 절약할 수 있습니다. 단, 이 경우 시간은 조금 더 소요될 수 있습니다.

입력값은 현재값만 사용한다 → 3개
dp 또한 바로 직전의 값과 현재의 값만 필요하다. → 2x3개, 2x3개
총 : 15개

정말 아주 조금만 더 생각해보는걸로 바로 총 90만개에서 15개로 메모리를 줄일 수 있었다.

이런 메모리제이션 문제에서 대부분 넉넉히 배열을 썼는데 다시 생각하게 해준 문제였다. 👀

    bool idx = true;
    for(int i=1; i<=N; ++i)
    {
        std::cin >> arr[0] >> arr[1] >> arr[2]; // 현재값만 사용

        // idx 현재
        // !idx 직전
        max_dp[idx][0] = std::max(max_dp[!idx][0], max_dp[!idx][1]) + arr[0];
        min_dp[idx][0] = std::min(min_dp[!idx][0], min_dp[!idx][1]) +  arr[0];

        max_dp[idx][1] = std::max(std::max(max_dp[!idx][0], max_dp[!idx][1]), max_dp[!idx][2]) + arr[1];
        min_dp[idx][1] = std::min(std::min(min_dp[!idx][0], min_dp[!idx][1]), min_dp[!idx][2]) + arr[1];

        max_dp[idx][2] = std::max(max_dp[!idx][1], max_dp[!idx][2]) + arr[2];
        min_dp[idx][2] = std::min(min_dp[!idx][1], min_dp[!idx][2]) + arr[2];

        idx = !idx; // toggle
    }

+ 최대, 최대 배열도 하나의 배열만 선언한 후, 재사용하면 메모리를 더 아낄 수 있습니다. 시간을 2배로 쓰겠지만 일단 제출 시 시간초과는 아니네요

💾 소스

#include <iostream>

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    int N;
    std::cin >> N;

    int arr[3] = {0, };
    int max_dp[2][3] = {0, };
    int min_dp[2][3] = {0, };
    
    bool idx = true;
    for(int i=1; i<=N; ++i)
    {
        std::cin >> arr[0] >> arr[1] >> arr[2];

        max_dp[idx][0] = std::max(max_dp[!idx][0], max_dp[!idx][1]) + arr[0];
        min_dp[idx][0] = std::min(min_dp[!idx][0], min_dp[!idx][1]) +  arr[0];

        max_dp[idx][1] = std::max(std::max(max_dp[!idx][0], max_dp[!idx][1]), max_dp[!idx][2]) + arr[1];
        min_dp[idx][1] = std::min(std::min(min_dp[!idx][0], min_dp[!idx][1]), min_dp[!idx][2]) + arr[1];

        max_dp[idx][2] = std::max(max_dp[!idx][1], max_dp[!idx][2]) + arr[2];
        min_dp[idx][2] = std::min(min_dp[!idx][1], min_dp[!idx][2]) + arr[2];

        idx = !idx;
    }

    int max_score = 0, min_score = 1e9;
    for(int i=0; i<3; ++i)
    {
        max_score = std::max(max_score, max_dp[!idx][i]);
        min_score = std::min(min_score, min_dp[!idx][i]);
    }

    std::cout << max_score << " " << min_score;

    return 0;
}

저작자표시 비영리 변경금지 (새창열림)