[BOJ] 백준 16288. Passport Control

알고리즘 스터디에서 나온 문제이다.

코드포스와 형식이 비슷해보여서 코포 연습 겸 블로그에 포스팅해보려 한다.

문제는 아래와 같다.

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

16288번: Passport Control

BOJ 16288. (from ICPC 2018 Seoul Regional)

문제가 잘 이해가 안돼서 [3, 1, 2]의 경우는 언제 가능한지 궁금했는데, Q1 (첫번째 통로)에 1, 2 /  Q2에 3을 이동시킨 후에 출구로는 2번째 통로에서부터 나오게 하면 된다.

---

의식의 흐름 및 해설

이민을 가려 하는 사람들을 K개의 통로로 이동시키되, K개의 통로에서 나오는 방법은 가지각색이다. 이 통로는 FIFO이므로 큐의 성질을 가지고 있다. 그래서 처음에는 N, K 제한도 작았기 때문에 자료구조를 활용한 문제인 줄 알았다. 그렇지만, queue를 사용하여 문제를 해결하기에는 너무 많은 경우의 수가 가능했다. N명이 K개의 통로를 매번 자유롭게 선택할 수 있고, 몇 번째 통로에서 사람이 나올지 자유롭게 결정할 수 있기 때문이다.

 

따라서 다른 방법을 생각해야 했다. 하나의 통로에는 증가하는 수열로 이루어져야 한다. 그 말은, 입력으로 주어지는 수열 중 a[i-1] > a[i]인 경우가 있으면 다른 통로에 들어가야 했다. 그렇기 때문에 처음에는 a[i-1] > a[i]인 경우를 카운트해주어 K보다 크면 NO를 띄워주도록 했다. 그러나 이 풀이는 아래와 같은 반례가 존재한다.

10 2
1 6 2 7 3 8 4 9 5 10
ans: YES
wrong: NO

// 1번 통로: 1 2 3 4 5
// 2번 통로: 6 7 8 9 10

a[i-1] > a[i]인 경우가 4번 나타나지만, 위 경우는 NO가 아니라 YES이다. 

 

위 경우는 증가하는 수열이 최소한으로 2개 가능하다. 조금 더 생각해보니 증가 수열은 최대한 한 통로에 집어넣을 수 있으므로 증가수열의 최소 개수가 K 이하이면 YES, 아니면 NO가 정답이었다.

 

그리고 생각해보면 증가 수열의 최소 개수가 K라는 것은, 다시 말해 LDS(최장 감소 부분 수열)의 길이가 K라는 것과 동일하다. 단순히 증가하는 수열이 있다고 하자. 중간에 a[i-1] > a[i]가 되도록 수를 하나 집어넣자. 그러면 a[i-1] > a[i]인 수가 증가했으므로 LDS의 길이도 1 증가한다. 다시 a[i-1] > a[i]인 수를 하나 집어넣어보자. 방금 집어넣은 경우보다 왼쪽에 집어넣든, 오른쪽에 집어넣든 LDS의 길이는 1 증가한다. 따라서 증가수열의 최소 개수가 K일 때, LDS의 길이는 K이다.

---

코드

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define int long long
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
const int MAX = 1e2+7;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int N,K,a[MAX];
bool vis[MAX];
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>N>>K;
    for (int i = 1; i <= N; i++) {
        cin>>a[i];
    }
    int cnt,res=0;
    for (cnt = 0; res < N; ++cnt) {
        int n=0,idx=0;
        for (int j = 1; j <= N; j++) {
            if(vis[j])continue;
            if(idx<j&&n<a[j]){
                idx=j;
                n=a[j];
                res++;
                vis[j]=true;
            }
        }
    }
    cout<<(cnt<=K?"YES":"NO")<<"\n";
}

---

증가 수열의 최소 개수랑 LDS 개수가 동일하다는 것을 생각해내는 데에 오래 걸렸다.

또한, 어떠한 경우가 YES일지 파악해내는 데에도 꽤 시간이 걸렸다. 그리디, 애드혹 쪽 감각을 길러줘야겠다.