[BOJ 1201] NMK

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

N,M,K가 주어졌을때 1~N까지의 수중에서 최대 부분 증가 수열의 길이가 M이고, 최대 부분 감소 수열의 길이가 K인 수열을 구하는 문제이다.

먼저 적어도 M개는 증가수열이 될것이고 , K는 감소수열이 될것이며 , 최대 겹칠수 있는 경우의 수는 1가지 경우이므로 N>=M+K-1의 전제조건을 만족 해야한다.

이후에 접근 방법을 생각한다면

1) 1~N까지의 숫자를 오름차순으로 정렬 후 해당 배열을  M개의 그룹으로 나눈다.

2) 이 때, 각 그룹에 들어있는 수의 개수는 K보다 작거나 같아야 하며 , 주어진 조건을 만족시키기 위해서 한 그룹은 K개의 수를 가지고 있어야 한다. 

3) 그 후 각 그룹을 뒤집어 주면 된다. 

예를들어 5 3 2 라는 입력이 주어진다면 1 2 3 4 5를 [1]  [2 3]   [4 5] 이렇게 임의로 3그룹으로 나누게 된다. 

그리고 각 그룹을 reverse하게 되면 [1]  [3 2]  [5 4] 이렇게 나뉘게 되고 최장 증가 길이는 3, 최장 감소 길이는 2가 되는 방식이다. 

하지만 이렇게 마무리를 하게되면 안된다. 생각을 더해보자. 비둘기 집의 원리가 무엇일까 ? n+1개의 물건을 n개에 넣을 떄 최소 하나는 2개 이상의 물건이 들어가게 된다는 것이다.

이를 이 문제와 함께 생각하게 되면 만약 M*K+1개의 물건을 M*K개에 나누게 되면 적어도 하나는 2개이상이 들어간다는 것이다. 따라서 문제의 조건에 N<=M*K라는 조건이 추가되어야 한다. 

#include <cstdio>
#include <algorithm>
using namespace std;
 
int a[505];
 
int main() {
    int i, j, k, l, m, n;
    scanf("%d%d%d", &n, &m, &l);
    if (n > m * l || n + 1 < m + l) {
        puts("-1");
        return 0;
    }
    for (i = 0; i < n; i++) a[i] = i + 1;
    j = 0;
    for (i = 1; i <= m; i++) {
        k = min(j + l, n - m + i);
        reverse(a + j, a + k);
        j = k;
    }
    for (i = 0; i < n; i++) printf("%d ", a[i]);
}

BOJ cubelover 님의 코드가 너무 간결해서 참고해 왔다. 깔끔쓰