BOJ)1201 NMK

문제: icpc.me/1201

N M K 가 주어질 때 1~N까지의 수로 이루어진 수열에서 최대 부분 증가 수열의 길이가 M이고 최대 부분 감소 수열의 길이가 M인 수열을 출력하는 문제이다.

우리는 부분 감소 수열의 개수 K개의 세그먼트를 만들면서 하나의 세그먼트는 전부 증가하는 수로 이루어져 있으며 그 세그먼트의 최대 길이는 M이 되도록 만들어주면 된다.

M+K-1<=N<=M*K 를 만족해야만 수열을 만들어줄 수 있으며

그리디하게 1~N의 수를 수열에 거꾸로 삽입해준 뒤에 뒤의 M만큼의 수를 1번 뒤집어 준 수열이 M+K-1==N인 경우이다.

이어서 K개의 감소 세그먼트를 만든다고 생각하면서 적당히 수를 뒤집어주면 수열을 완성가능하다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, k, a[501], f;
int main() {
    scanf("%d%d%d", &n, &m, &k);
    if (!(m + k - 1 <= n) || !(n <= m*k)) {
        puts("-1");
        return 0;
    }
    for (int i = 1; i <= n; i++)
        a[n - i] = i;
    reverse(a + n - m, a + n);
    int c = n - m + 1;
    f = 1;
    while(c != k) {
        int r = c - k;
        int v = r / m;
        if (v) {
            reverse(a + n - m*(f + 1), a + n - m*f);
            f++;
            c -= m - 1;
        }
        else {
            reverse(a + n - m*f - r - 1, a + n - m*f);
            break;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}