[백준] 1201 – NMK

문제

1201: NMK(acmicpc.net)

설명

문제만 읽으면 꽤 간단해 보이지만 구현 방법은 정말 애매한 문제..

첫 번째 조건문은 N이 M과 K보다 크거나 N+1이 M+K보다 작으면 시퀀스를 구성할 수 없고 만들 수 없는 경우입니다.

4 2 2가 주어지면 {2 1} {4 3}과 같은 시퀀스를 만들 수 있지만 5 2 2가 주어지면 그렇게 할 수 없습니다.

4 4 2의 경우 LIS는 만들 수 있지만 LDS는 만들 수 없으므로 이 역시 -1을 출력해야 합니다. 감소할 때 증가하는 수열이 있을 수 없기 때문입니다.

이제 Sequence라는 배열을 만들고 1에서 N까지의 숫자를 오름차순으로 정렬합니다. 오름차순이므로 LIS가 이미 풀렸다고 가정할 수 있습니다.

그리고 시퀀스를 M 그룹으로 나눕니다. M개의 그룹으로 나눈 이유는 각 그룹에서 숫자를 고르면 M개의 증가하는 시퀀스를 형성할 수 있기 때문입니다.

쉽게 말해 이미 오름차순으로 정렬된 1부터 N까지 순서대로 어떤 숫자를 고르면 오름차순으로 나오는 것과 같은 원리이다.

그리고 이 그룹의 모든 숫자를 내림차순으로 정렬합니다. 역함수를 사용하여 이를 수행할 수 있습니다.

이렇게 하면 모든 사람이 LDS가 되고 LIS가 사라지는 것처럼 보이지만 각 그룹의 첫 번째 숫자를 보면 여전히 LIS가 보입니다.

그렇게 하고 전체 시퀀스를 출력하면 이것이 정답입니다.

#include <iostream>
using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    if (N > M * K || N + 1 < M + K) {
        cout << "-1";
        return 0;
    }
    
    int sequence(N+1);
    for (int i = 1; i <= N; i++) {
        sequence(i) = i;
    }
    
    int start = 1;
    for (int i = 1; i <= M; i++) {
        int temp = min(start+K, N-M+i+1);
        reverse(sequence+start, sequence+temp);
        start = temp;
    }
        
    for (int i = 1; i <= N; i++) {
        cout << sequence(i) << " ";
    }
    
    return 0;
}