[백준] 1201번 NMK Java

문제 링크

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

문제

1부터 N까지의 수를 한 번씩 이용해서 가장 긴 증가하는 부분 수열의 길이가 M이고, 가장 긴 감소하는 부분 수열의 길이가 K인 수열을 출력한다

입력

첫째 줄에 세 정수 N, M, K가 주어진다.

출력

첫째 줄에 문제의 조건을 만족하는 수열을 출력한다. 만약, 조건을 만족하는 수열이 없다면 -1을 출력한다.

제한

1 ≤ N ≤ 500
1 ≤ M, K ≤ N

알고리즘: 그리디

풀이

증가하는 수열이 있으면 그 수열 중 하나는 감소하는 수열에 수로 포함될 수 있다.
ex) 7 8 9 4 3 -> 7 8 9는 증가하는 수열이고 이 중 하나를 포함해서 9 4 3이런 식으로 감소하는 수열에 포함될 수 있음.
일단 조건을 만족하는 수열의 범위를 구해야 한다.
예제의 4 4 2를 보면 -1을 출력한다. 4개를 증가하는 수열에 쓰이고 그중 하나는 감소하는 수열에 포함된다고 해도 수 하나가 부족하다. 4 3 3을 해봐도 똑같이 수가 하나 부족하다. 그 이유를 보면 각 그룹(내림차순 그룹, 오름차순 그룹)은 수 하나를 공유한다. M이 4이면 수를 하나 공유하고 남은 N-M개를 포함해서 K 길이의 내림차순을 만들어야 하는데 수가 하나 부족한 것을 볼 수 있다.
그래서 수가 부족하지 않고 조건을 만족하려면 N+M <= N+1을 만족해야 한다. 그다음 현재 N에서 M,K가 어디까지 작아질 수 있나 확인해야 한다. 9 3 2인 N M K를 보자 조건을 만족하면서 수를 만들기 위해서 길이가 같은 증가 수열을 최대한으로 만들어야 해당 조건에 가장 근접할 수 있다.
그래서 길이가 3인 증가 수열을 2개 만들면 M K를 만족하는데 7 8 9 4 5 6 나머지 수 3개를 어디에도 추가할 수 없게 된다. (추가하면 조건이 무너짐) 나머지 수 3개를 이용해서 증가하는 수열을 추가하면(N인 9를 만족하면서 최대한 같은 길이의 증가 수열을 중복되게) 7 8 9 4 5 6 1 2 3으로 M,K가 3 3이 되는데, 그 조건이 N <= M K임을 알 수 있다.
결론적으로 조건을 만족하는 수열의 범위는 (N + M -1 <= N <= M K)으로 이 범위를 벗어난다면 -1을 출력한다.
조건을 만족한다면,
ex) 13 5 4
1.K부터 K개를 내림차순으로 수를 만든다.
->4 3 2 1
2. 나머지 수 13 - 4 = 9개고 5개(M)을 만족하려면 길이가 4인 증가 수열이 필요하다.
4인 증가 수열을 반복적으로 최종 수열에 추가하고, 길이가 4가 아니더라도 증가 수열이 4를 넘어가지 않기 때문에 4보다 작은 증가 수열도 최종 수열에 추가한다.
->4 3 2 1 10 11 12 13 6 7 8 9 5
최종 수열을 보면 NMK 조건을 만족하는 수열임을 알 수 있다.

이 문제를 푸는데 상당히 많은 시간이 걸렸다. 스스로 풀었지만 확신하면서 풀지는 못했다. 풀이를 찾아보니 Erdos-Szekeres 정리를 알면 더 쉽게 푼다고 한다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, K;
    static boolean end = false;
    static StringBuilder ans = new StringBuilder();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        if ((M + K - 1 <= N) && (N <= M * K)) {
            for (int i = K; i >= 1; i--) {
                ans.append(i);
                ans.append(" ");
            }
            while (!end) {
                Stack<Integer> stack = new Stack<>();
                if(N < N - (M - 2)) end = true;
                for (int i = N; i >= N - (M - 2); i--) {
                    if(K == i) {
                        end = true;
                        break;
                    }
                    stack.push(i);
                }
                while(stack.size() != 0) {
                    ans.append(stack.pop());
                    ans.append(" ");
                }
                N = N - (M - 2) - 1;
            }
            System.out.println(ans.toString().trim());
        } else System.out.println(-1);
    }
}