백준 1201 NMK C++

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

1201번: NMK

1부터 N까지 수에 대해 가장 긴 증가하는 부분 수열 길이가 M, 가장 긴 감소하는 부분 수열 길이가 K가 되도록 수열을 만드는 문제입니다.

 

M*K 만큼 0으로 초기화된 배열에 K 간격으로 1부터 M까지 수를 넣고, 역순으로 나머지 수 중 큰 수를 차례로 넣게 되면 M, K 조건을 모두 만족하게 됩니다. 

예를 들어, 10, 5, 4와 같은 경우

0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 로 이루어진 배열이 있고

0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 10 9 8 5

0 0 0 1 0 0 0 2 0 0 0 3 7 6 0 4 10 9 8 5 

=> 1 2 3 7 6 4 10 9 8 5 와 같이 수열을 만들 수 있습니다.

 

안 되는 경우로는

1) 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열은 적어도 하나의 원소를 공유하기 때문에 N >= M + K - 1 이어야 합니다.

2) 그리고 비둘기집 원리에 의해 N >= M * K + 1 인 경우, 가장 긴 증가하는 부분 수열 길이는 >= M + 1, 가장 긴 감소하는 부분 수열 길이는 >=  K + 1 이 되므로 조건을 만족할 수 없습니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, k;
vector<int> vec;
vector<bool> check;

void init()
{
    cin >> n >> m >> k;
    
    vec.resize(m * k);
    check.resize(n + 1, false);
    check[0] = true;
    
    for(int i = 1; i <= m; i++) {
        vec[i * k - 1] = i;
        check[i] = true;
    }
}

void calc()
{
    for(int i = n; i > 0; i--) {
        if(check[i])
            continue;
        
        int chk = 0;
        int idx = -1;
        for(int j = m * k - 1; j >= 0; j--) {
            if(vec[j] == 0 && chk == 0) {
                chk = 1;
            }
            
            else if(vec[j] != 0 && chk == 1) {
                idx = j + 1;
                break;
            }
        }
        
        // idx가 맨 앞에 0 가리키는 경우 
        if(chk == 1 && idx == -1) {
            idx = 0;
        }
        
        // 더 이상 수 넣기 불가능한 경우
        else if(idx == -1) {
            break;
        }
        
        for(int j = 0; j < k - 1; j++) {
            if(check[i - j] == false) {
                vec[idx + j] = i - j;
                check[i - j] = true;
            }
        }
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // 일단 1 ~ m 으로 k 간격으로 가장 긴 증가하는 수열 생성
    // 그리고 나머지 칸에 큰 수 순으로 대입하여 가장 긴 감소하는 수열 길이 k 되도록
    
    init();
    
    // 비둘기집 원리에 의해 안 되는 경우 
    if(m + k - 1 > n || n > m * k) {
        cout << -1;
        return 0;
    }
    
    // k=1 인 경우 
    if(k == 1 && n == m) {
        for(int i = 1; i <= n; i++) {
            cout << i << ' ';
        }
        return 0;
    }
    
    calc();
    
    for(auto v : vec) {
        if(v != 0) {
            cout << v << ' ';
        }
    }
    
    return 0;
}