BOJ 27577 - Everything is A Nail

 

 

문제 링크

• 27577번: Everything Is A Nail

 

문제 풀이

 

오랜만에 BOJ를 탐닉하다... 사람들이 풀고 있길래... 찍먹을 해보게 되었습니다..

간단하게 설명하면, 처리해야 하는 작업의 종류가 0, 1, 2 세 가지가 있고, 각 작업이 순서대로 주어집니다.

이때, 작업을 처리해야 하는 도구가 존재하고, 첫 번째 도구는 마음대로... 그리고 다른 도구들로 한 번씩 변경 가능합니다.

 

즉, 배열안을 세 파티션으로 나눈 다음, 각각의 지정된 원소가 몇 개 있는지 총합한 값을 최대로 만드는 문제로 바라볼 수 있겠습니다.

 

근데 도구 선택이 자유로우므로, 도구를 드는 순서 3! 번 다 정하고 해보면 되겠습니다.

 

다르게 풀수도 있지만, 상위문제에서는 이런 유형의 문제가 많이 존재하는데요. 거의 작업종류가 엄청 많게 하고, 조금 더 응용이 들어가는 문제들이 많이 나옵니다.

 

상위 문제에서 자주 쓰는 dp 테크닉을 가져와 봅시다.

 

$dp[i][j]$를 $i$번째 도구로 $j$번째까지 일을 하고 도구를 교체하기 전의 일을 처리한 최대 값이라고 정의합시다.

 

나이브하게 식을 한번 세워봅시다.

 

$$dp[i][j] = \max_{k \; < \; j} \bigg(dp[i-1][k] + \sum_{g=k+1}^{j} \big(\; 1 \;\;\; \text{if g'th task is i}\big)\bigg)$$

 

이러면 일단 $O(N^3)$ 입니다. 최적화를 시작해 봅시다. 일단 안쪽의 $k+1$번째부터 $j$번째 존재하는 $i$종류의 작업의 개수는 Prefix Sum (누적합)을 이용하여, 쉽게 구할 수 있습니다. 고쳐봅시다.

 

$\text{prefix}[i][j]$ 를 $j$번째까지 존재하는  종류가  $i$인 작업의 갯수라고 정의합시다.

 

$$dp[i][j] = \max_{k \; < \; j} \bigg(dp[i-1][k] + \text{prefix}[i][j]  - \text{prefix}[i][k] \bigg)$$

 

이렇게 하면, 구간에 존재하는 종류가 $i$인 작업의 갯수를 $O(1)$에 구할 수 있습니다. 하지만 여전히 시간복잡도는 $O(N^2)$입니다. 어떻게 해결해야 할까요?

 

dp점화식에서 상수로 작용하는 부분을 한번 빼볼까요!

$$dp[i][j] = \max_{k \; < \; j} \bigg(dp[i-1][k]  - \text{prefix}[i][k] \bigg) + \text{prefix}[i][j]$$

 

$\max$ 함수 안쪽에 있는 $ dp[i-1][k]  - \text{prefix}[i][k]$ 을 하나의 배열로 다시 만들어 봅시다.

 

$$dp[i][j] = \max_{k \; < \; j} \big( A[k] \big)+ \text{prefix}[i][j]$$

 

$j$에 대해서 왼쪽에 있는 $A[k]$는 선형시간에 한 번에 밀면서 구할 수 있습니다. 이런 식으로 최적화를 걸면 $O(N)$에 점화식을 구할 수 있습니다.

 

여기서 중요한 테크닉은 prefixSum에서 상수를 구분하고 뺀 다음, 상수가 아닌 부분은 배열처리를 새롭게 하는 부분입니다. 꼭 기억해 두세요~

 

#include<bits/stdc++.h>

using namespace std;

int prefix[3][303030], N;

vector<int> ord;

int solve () {
    vector<int> A(303030), B(303030);

    for (int i=0;i<N;i++) {
        A[i] = prefix[ord[0]][i] - prefix[ord[1]][i];
    }

    for (int j=1;j<=2;j++) {
        int mx = 0;
        for (int i=0;i<N;i++) {
            B[i] = prefix[ord[j]][i] + mx;
            mx = max(mx, A[i]);
        }

        swap(A, B);
        std::fill(B.begin(), B.end(), 0);

        if (j == 2) break;

        for (int i=0;i<N;i++) {
            A[i] -= prefix[ord[j+1]][i];
        }
    }

    return A[N-1];
}

int ans = 0;

void rec (int depth) {
    if (depth == 3) {
        ans = max(solve(), ans);
        return;
    }

    for (int i=depth;i<3;i++) {
        swap(ord[i], ord[depth]);
        rec(depth+1);
        swap(ord[i], ord[depth]);
    }
}

int main () {
    cin >> N;

    ord.push_back(0);
    ord.push_back(1);
    ord.push_back(2);

    for (int i=0;i<N;i++) {
        int g; cin >> g;
        prefix[g][i]++;
    }


    for (int i=0;i<N;i++) {
        for (int  j : {0, 1,  2}) {
            prefix[j][i+1] += prefix[j][i];
        }
    }

    rec(0);

    cout << ans;

}