백준 1201 파이썬, 자바 - NMK

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

1201번: NMK

문제

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

코드

import sys
n, m, k = map(int, sys.stdin.readline().split())
def ans(n, m, k):
    arr = list(range(k, 0, -1))
    n -= k
    m -= 1
    while m:
        arr.extend(range(k + n // m, k, -1))
        k += n // m
        n -= n // m
        m -= 1
    return list(map(str, arr))
sys.stdout.write('-1' if n < m + k - 1 or n > m * k else ' '.join(ans(n, m, k)))

.

import java.io.*;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.util.stream.Collectors.toList;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        if (n < m + k - 1 || n > m * k) {
            bw.write("-1");
        }
        else{
            bw.write(String.valueOf(sb.append(ans(n, m, k).stream().map(String::valueOf).collect(Collectors.joining(" ")))));
        }
        bw.flush();
        br.close();
        bw.close();
    }

    public static List<Integer> ans(int n, int m, int k) {
        List<Integer> arr = IntStream.iterate(k, i -> i > 0, i -> i - 1).boxed().collect(toList());
        n -= k;
        m -= 1;
        while(m != 0) {
            int nm = n / m;
            int tmpK = k;
            IntStream.iterate(tmpK + nm, i -> i > tmpK, i -> i - 1).forEach(arr::add);
            k += nm;
            n -= nm;
            m -= 1;
        }
        return arr;
    }

}

풀이

이 문제는 lis, lds를 이해해야 풀 수 있는 문제였다. 사실 문제 설명만 읽어도 그럴 것이라 알 수 있다. 맨 처음에 구할 수 없는 경우 -1 을 출력하고, 아닌 경우 계산을 수행했다.