백준 18214번 Reordering the Documents

문제 요약

크기가 $N$인 문서 더미가 주어진다. 각 문서에는 $1$부터 $N$까지 수가 부여되어 있다. 문서 더미는 스택과 같은데 놓여있는 문서들의 순서는 뒤죽박죽이다.

이 때, 이 문서들을 다른 두 개의 임시 문서 더미로 옮긴 뒤에 정리하는 방식으로 문서 더미의 위에서부터 $1$부터 $N$까지로 차례대로 놓여있는 문서 더미를 만들려고 한다. 임시 문서 더미들은 최대 $M$의 높이를 가질 수 있다.

이 때, 서로 다른 두 개의 임시 문서 더미에 문서들을 놓는 경우의 수를 구하여라 .

$ 1 \le N \le 5000$, $ N/2 \le M \le N$

문제 요약이 잘 안된다. 링크

풀이

일단 처음의 문서 더미의 위에서부터 아래로 내려가는 순으로 문서들의 번호가 주어진다. 그리고 서로 다른 두 개의 스택으로 이것들을 전부 옮긴 뒤에 다시 정렬된 상태로 문서 더미를 정리하려면 두 개의 임시 스택은 위에서부터 아래로 내려가면서 숫자가 줄어들어야 한다.

이를 생각해보면 결국 길이 $N$의 수열에서 길이가 $M$이하인 두 개의 증가 부분 수열로 분할 하는 것과 동일하다. 처음 문서더미의 문서들의 수를 $a$라고 하자.

이제 문서들을 하나씩 놓는다고 생각해보자. 일단 임시 스택들은 제일 위의 원소가 해당 스택에서 가장 큰 원소가 되어야 한다. 그러면 $a_i$를 놓을 때 두 스택 중 하나의 최상단 원소가 $a_i$보다 크다면 $a_i$를 놓을 수 없다. 즉, 어디에 놓아야 할 지 정해진다.

이를 생각해보면 애초에 위 과정이 가능한지 불가능한지도 $a_i$를 놓을 때 판단할 수 있다. $\min{a_j} (j>i)$가 $a_i$보다 작다면, 그러한 문서는 두 스택 어느 곳에도 놓일 수 없다. 따라서, 불가능한 경우임을 바로 알 수 있다.

이제 $a_i$가 두 스택의 최상단 원소보다 크다고 하자. 일단 두 스택 중에 더 최상단 원소가 더 큰 스택에는 $a_i$를 놓아도 상관 없다. 그러면 $a_i$를 더 작은 원소가 있는 스택에 놓게 되면 어떻게 될까?

만약에 $\min{a_j}(j>i)$가 더 큰 원소보다 작다면 이 원소는 결국 두 스택 전부에 놓을 수 없는 원소가 될 것이다.

따라서, $a_i$를 더 작은 스택에 놓을 수 있는 조건은 $a_i$ 이후의 최솟값이 다른 큰 스택보다 커야한다는 것이다.

이거로 문서 더미에서 문서 하나 $a_i$를 꺼낼 때 일어날 수 있는 모든 경우의 수를 살펴봤다. 결국 중요한 것은 $a_i$ 이전에 놓은 문서들 중에서 가장 큰 수이다. 그리고 조건이 하나 더 있었는데 높이가 $M$보다 높아지면 안된다는 것이었다.

이를 고려하기 위해서 가장 큰 원소가 놓여있는 스택의 높이가 $h$일 때의 경우의 수를 저장해두면 모든 경우의 수를 계산할 수 있다.

$dp(i, j)$를 $1...i$까지 문서를 놨을 때 가장 큰 수를 가지는 문서가 놓인 스택의 높이가 $j$일 때의 경우의 수로 놓자.

그러면 최종 답은 $\sum_{i=1}^M dp(N, i)$가 된다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
int N, M;
int a[5005], mn[5005], mx[5005];

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  cin >> N >> M;
  for(int i=1;i<=N;++i) cin >> a[i];
  for(int i=1;i<=N;++i) mx[i] = max(mx[i-1], a[i]);
  mn[N] = N+1;
  for(int i=N-1;i>0;--i) mn[i] = min(mn[i+1], a[i+1]);
  vector<ll> dp_cur(M+1), dp_prev(M+1);
  dp_cur[1] = 2;
  for(int i=2;i<=N;++i) {
    dp_prev = dp_cur;
    if(mx[i] > a[i]) {  // should place a_i on lower one
      if(mn[i] < a[i]) {
        cout << 0 << '\n';
        return 0;
      }
      for(int j=1;j<=min(i,M);++j) {
        if(max(j, i-j) <= M) dp_cur[j] = dp_prev[j];
        else dp_cur[j] = 0;
      }
    }
    else {  // a_i is max element so far
      for(int j=1;j<=min(i, M);++j) {
        if(max(j, i-j) <= M) dp_cur[j] = dp_prev[j-1];
        else dp_cur[j] = 0;
      }
      if(mx[i-1] < mn[i]) { // mx[i-1] is on higher
        for(int j=1;j<=min(i,M);++j) {
          if(max(j, i-j) <= M) {
            dp_cur[j] += dp_prev[i-j];
            dp_cur[j] %= mod;
          }
        }
      }
    }
  }
  ll ans = 0;
  for(int i=1;i<=M;++i) ans = (ans + dp_cur[i]) % mod;
  cout << ans << '\n';
  return 0;
}