BOJ 27244 - Монотонная подпоследовательность (G1)

사용 알고리즘

Greedy-Style Constructive

 

풀이

문제를 아주 짧게 요약하면 다음과 같다.

N, K (<=10^6)이 주어질때, max(LIS길이, LDS길이) = k인 길이 N의 순열을 아무거나 출력한다.

하나에만 초점을 맞추자. 여기서는 LDS에 초점을 맞추겠다.

LDS가 정확히 k이려면 어떻게 순열을 구성해야 할까?

위처럼 연속된 K개의 값이 감소하게 이루어지면 된다.

그렇다면 LDS<K+1이 되게 하려면 어떻게 구성해야 할까? 정답은 A+1 뒤에 A+1 미만의 값이 없으면 된다.

이렇게 하면서 LIS<K+1이 되게 하려면 어떻게 구성해야 할까?

이렇게 구성하면 LIS는 크기 K인(정확히는 K 이하) 각 그룹에서 하나씩밖에 선택될 수 없다. 따라서 이러한 그룹의 개수가 LIS의 길이이고, 그 길이가 K 이하이면 된다.

크기 K인 각 그룹의 개수가 K개 이하여야 하므로, K*K<N이면 불가능함을 알 수 있고, 그 외의 경우에는 위와 같이 답을 구성하면 된다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000009
ll n, k;
int main(){
    fast;
    cin>>n>>k;
    if(k*k<n)return cout<<-1, 0;
    ll cur = k;
    vector<ll> ans(n+1, 0);
    ll cnt = 1;
    ll cnt2 = 0;
    for(int i = 1 ; i <= n ; i++){
        ans[i]=cur--;
        if(++cnt2==k){
            cnt++;
            cnt2=0;
            cur = min(n,k*cnt);
        }
    }
    for(int i = 1 ; i <= n ; i++)cout<<ans[i]<<" ";
}

이 풀이를 확장하면 P3인 NMK (https://www.acmicpc.net/problem/1201)을 풀 수 있다.

퍼솔 냠