BOJ 18214 Reordering the Documents

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/18214
• 번역

문제 번역

#

Susan은 식탁 정리는 잘하지만, 사무실 책상 정리는 잘 못합니다.

Susan은 방금 일련의 문서들에 대한 서류 작업을 마쳤고, 문서들은 여전히 책상에 쌓여 있습니다. 문서들은 일련번호가 있으며, 상사가 가져왔을 때는 순서대로 쌓여 있었습니다. 그러나 지금은 순서가 완벽하지 않은데, Susan이 너무 게을러서 더미에서 빠져나온 문서들을 제자리에 다시 넣지 않았기 때문입니다. 작업이 끝났다는 소식을 듣고, 상사는 그녀에게 보내고 있는 문서 상자에 문서들을 즉시 반납하기를 원합니다. 물론 문서들은 일련번호 순서대로 상자에 보관되어야 합니다.

책상에는 두 개의 문서 더미를 더 놓을 공간만 있어서, Susan은 두 개의 임시 더미를 만들 계획입니다. 현재 더미의 모든 문서들은 위에서부터 하나씩 두 임시 더미 중 하나로 옮겨져야 합니다. 서둘러 이 더미들을 너무 높게 만들면 무너질 수 있으므로, 너무 많은 문서를 쌓아서는 안 됩니다. 모든 문서를 임시 더미로 옮기고 문서 상자를 받은 후, 두 더미의 문서들은 위에서부터 하나씩 상자로 옮겨집니다. 문서들을 순서대로 상자에 넣으려면, 두 더미에서 일련번호의 역순으로 있어야 합니다.

예를 들어, 더미에 위에서부터 순서대로 1, 3, 4, 2, 6, 5의 6개 문서가 있고, 임시 더미에는 최대 3개의 문서만 쌓을 수 있다고 가정합니다. 그러면 그녀는 두 개의 임시 더미를 만들 수 있는데, 하나는 위에서부터 6, 4, 3 문서를 가지고, 다른 하나는 5, 2, 1을 가집니다 (그림 E.1). 두 임시 더미 모두 역순으로 정렬되어 있습니다. 그런 다음 두 임시 더미의 맨 위 문서의 일련번호를 비교하여, 더 큰 번호를 가진 것(이 경우 #6)을 먼저 제거하여 문서 상자에 보관합니다. 이것을 반복하면 모든 문서가 문서 상자에 완벽하게 순서대로 정렬됩니다.

Susan은 현재 더미의 문서들로 이 계획이 실제로 실행 가능한지, 그렇다면 두 임시 더미에 쌓는 방법이 몇 가지나 되는지 궁금해합니다. 계획이 실행 불가능하면 0이어야 합니다.

더미의 각 문서는 두 임시 더미 중 하나로 옮겨질 수 있으므로, n개의 문서에 대해 총 2^n개의 서로 다른 선택 조합이 있지만, 그 중 일부는 임시 더미의 역순을 방해하여 부적절할 수 있습니다.

위에서 설명한 예는 샘플 입력의 첫 번째 케이스에 해당합니다. 이 경우, 마지막 두 문서인 5와 6은 목적지를 바꿀 수 있습니다. 또한 두 임시 더미의 역할을 완전히 교환해도 괜찮습니다. 다른 이동 순서는 더미 중 하나를 3보다 높게 만들거나 순서를 틀리게 만들 수 있으므로, 이 예에서 문서를 임시 더미에 쌓는 서로 다른 방법의 총 개수는 2 × 2 = 4입니다.

입력

#

입력은 다음 형식의 단일 테스트 케이스로 구성됩니다.

n m
s1 ... sn

여기서 n은 더미의 문서 수(1 ≤ n ≤ 5000)이고, m은 무너질 위험 없이 하나의 임시 더미에 쌓을 수 있는 문서 수(n/2 ≤ m ≤ n)입니다. s1부터 sn까지의 숫자는 문서 더미의 맨 위에서 맨 아래까지 문서의 일련번호입니다. 1부터 n까지의 모든 숫자가 정확히 한 번씩 나타나는 것이 보장됩니다.

출력

#

목적에 맞는 두 임시 더미를 만드는 방법의 수를 한 줄에 정수로 출력합니다. 가능한 선택이 없으면 방법의 수는 당연히 0입니다.

가능한 방법의 수가 10^9 + 7 이상이면, 방법의 수를 10^9 + 7로 나눈 나머지를 출력합니다.

🧐 관찰 및 접근

#

• LIS 두개로 분할하는 문제이다.
  • 이를 위해서 두 스택을 $A, B$라고 하면, $A$의 맨위 값, $B$의 맨위 값, $A$ 스택 안에있는 개수를 사용하면 $O(N^3)$ DP풀이는 나오는 것 같은데, 줄이기 쉽지 않아보인다.
• 그런데, 두 스택에 나누어 담는걸 다르게 생각해보자.
  • 어떤 두 수가 반전수$(i < j, A_i > A_j)$를 이룬다면 두 수는 같은 스택에 들어가선 안된다.
  • 이 관계를 간선으로 나타내면, 이분 그래프로 해석할 수 있겠다.
• 그렇다면 이분그래프에서 한 컴포넌트가 두가지 색으로 칠해진다면, 그 개수를 $m, n$이라고 해보자.
  • 각 스택에 $m$개 혹은 $n$개가 추가되어야 한다.
  • 이는 배낭 문제로 해석할 수 있다!

💻 풀이

#

• 코드 (C++):

pii coloring(int cur, int c){
    pii res = {0, 0};
    color[cur] = c;
    if(c == 1) res.first++;
    else res.second++;
    for(auto nxt: links[cur]){
        if(color[nxt] == 0){
            pii tmp = coloring(nxt, 3 - c);
            res.first += tmp.first;
            res.second += tmp.second;
        }
        else if(color[nxt] == c){
            return {-1e9, -1e9};
        }
    }
    return res;
}

void solve(){
    cin >> N >> M;
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, N) rep(j, i+1, N){
        if(S[i] > S[j]){
            links[i].push_back(j);
            links[j].push_back(i);
        }
    }
    vector<pii> groups;
    rep(i, 0, N) if(color[i] == 0){
        pii tmp = coloring(i, 1);
        if(tmp.first < 0){
            cout << 0;
            return;
        }
        groups.push_back(tmp);
    }

    vector<mint> DP(N+1, 0);
    DP[0] = 1;
    for(auto [a, b]: groups){
        vector<mint> nDP(N+1, 0);
        rep(i, 0, N+1){
            if(i+a <= N) nDP[i+a] += DP[i];
            if(i+b <= N) nDP[i+b] += DP[i];
        }
        swap(DP, nDP);
    }
    mint ans = 0;
    rep(i, 0, N+1) if(i <= M && (N-i) <= M) ans += DP[i];
    cout << ans;
}