BOJ 1201 - NMK (P3)

사용 알고리즘

Greedy-Style Constructive

 

풀이

BOJ 27244의 확장판이다.

https://sehujeong.tistory.com/20에서 설명한 그룹을 확장해보자.

그룹의 크기가 최대 K이고, 그 개수가 M개면 똑같이 풀 수 있을 것이다.

따라서 N을 K+a1+a2+...+a_M-1 꼴로 나타낼 수 있으면 27244와 똑같다.(1<=i<=M-1인 i에 대하여 1 <= a_i <= K이다) 저기서 k, a1, a2, ...가 의미하는것은 각 그룹의 크기이다. 그러한 그룹의 개수가 M개이므로 LIS의 길이는 M이고, LDS의 길이는 max(K, a1, a2, ..., a_M-1)이고 1<=a_i<=K이고 max(K, a1, a2, ..., a_M-1) = K가 되어 조건을 만족한다.

답을 구성할 수 없는 경우는 엄밀하지 않지만 어렵지 않게 증명할 수 있다.

#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, m, k;
int main(){
    fast;
    cin>>n>>m>>k;
    if(!(m+k-1<=n and n<=m*k))return cout<<-1, 0;
    vector<ll> ans;
    vector<ll> group;
    ll cur = n;
    for(int i = 1 ; i <= m ; i++){
        int j;
        for(j = k ; j>=1 ; j--){
            if(cur-j<m-i)continue;
            break;
        }
        group.push_back(j);
        cur -= j;
    }
    cur=0;
    for(int i = 0 ; i < m ; i++){
        ll x = group[i];
        while(x>0){
            ans.push_back(cur+x--);
        }
        cur += group[i];
    }
    for(auto i : ans)cout<<i<<" ";
}