[백준] 1201번 NMK - JAVA

문제

https://www.acmicpc.net/status?user_id=dlwogns3413&problem_id=1201&from_mine=1

풀이

풀이과정

간단해 보이지만 굉장히 어려운 문제였다. 해결 방법은 다음과 같다.

먼저 1부터 N까지의 수를 오름차순으로 정렬한다. (N = 13 M = 5 K = 4)
1 2 3 4 5 6 7 8 9 10 11 12 13

그다음에 N까지의 수를 M개의 묶음으로 나타내준다. 이때 한 묶음에 들어있는 개수는 최대 K개로 한다.
1 2 3 4 | 5 6 7 | 8 9 | 10 11 | 12 13

각 묶음을 내림차순으로 정렬해준다.
4 3 2 1 | 7 6 5 | 9 8 | 11 10 | 13 12
이떄 각 묶음에서 제일 처음 위치한 숫자끼리 모아보면 가장 긴 증가하는 부분 수열이 나오게 된다.
4 7 9 11 13
이렇게 되는 이유는 오름차순으로 정렬된 상태에서 M개의 묶음을 내림차순 해주었기 때문에
왼쪽에 있는 묶음은 오른쪽에 있는 묶음의 제일 큰 수 보다 작을 수 밖에 없기 때문이다.

즉, 한 묶음에 들어있는 최대 개수가 K개 이므로 가장 긴 감소하는 부분 수열의 길이의 최대는 K가 될 수 밖에 없고, M개의 묶음으로 나타내주었기 때문에 가장 긴 증가하는 부분 수열의 길이는 M이 될 수 밖에 없다.

답이 -1이 되는 경우

그러면 어떨때 조건을 만족못하는지 알아보자.
1) M개의 묶음으로 나타낼때 한 묶음에 들어있는 숫자의 개수는 최대 K개가되어야 한다. 즉 하나의 묶음에도 K보다 큰 수의 개수가 존재한다면 조건을 만족못하게 된다.
즉, N <= M * K가 되어야 한다.

2) 문제의 조건에 따르면 M과 K는 1이상이다 즉 무조건 가장 긴 증가하는 부분수열과 가장 긴 감소하는 부분수열이 있다는 이야기이다. 가장 긴 증가하는 부분수열과 가장 긴 감소하는 부분수열이 둘다 존재 한다는 이야기는 반드시 1개의 수를 공유를 해야한다는 뜻이된다.
즉, M + K - 1 <= N가 되어야 한다.

M개의 묶음으로 나누는 방법

일단, 적어도 한 개의 묶음에는 K개의 수가 들어있어여 하므로 먼저 K개의 수가 들어있는 묶음 하나를 확보한다. 그러면 이제 M-1개의 묶음을 만들어야 하고, 남은 수의 개수는 N-K개이다.

만약 (N = 13 M = 5 K = 4)라고 한다면 먼저 개의 수가 들어있는 묶음 하나를 확보한다.
(1 2 3 4) 나머지 수: 5 6 7 8 9 10 11 12 13 (9개)

5 6 7 8 9 10 11 12 13을 4개의 묶음으로 나누려면 하나의 묶음당 적어도 들어가는 수의 개수는 9/4개 즉 2개이다. 하지만 나머지가 존재하는데 이 나머지는 각각의 묶음마다 개수를 1 증가시켜 주는 형태로 배분해준다.
1 2 3 4 -> K개
5 6 7 -> (N-K) / (M-1) + 1개
8 9 -> (N-K) / (M-1)개
10 11 -> (N-K) / (M-1)개
12 13 -> (N-K) / (M-1)개

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    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());
    StringBuffer sb = new StringBuffer();
    if(N >= M+K-1 && N <= M*K) {
      int[] result = new int[M+1];
      result[1] = K;
      N = N - K;
      if(M - 1 > 0) {
        int minLength = N / (M - 1);
        int rest = N % (M - 1);
        for(int i=2; i<=M; i++) {
          if(rest >0) {
            result[i] = result[i-1] + minLength + 1;
            rest--;
          }else {
            result[i] = result[i-1] + minLength;
          }
        }
      }
      for(int i=1; i<result.length; i++) {
        for(int j=result[i]; j>result[i-1]; j--)  {
          sb.append(j).append(" ");
        }
      }
      System.out.println(sb);
    }else {
      System.out.println(-1);
    }
  }
}