[백준 1201번] NMK (java)

1201번: NMK

어려워서 오래 걸렸던 문제.. 다른 풀이를 참고해서 문제를 해결하였다.

 

해결 방법은 다음과 같다.

 

1. 1부터 N까지를 오름차순으로 정렬한다. (ex. N = 13, M = 5, K = 4)

 

 

2. 수열을 M묶음으로 나눈다. 이때 하나의 묶음에는 숫자가 K개 혹은 그 이하가 들어있어야 한다.

   또한, 적어도 하나의 묶음은 K개의 수가 존재해야 한다.

 

 

3. M개의 묶음으로 나누었으면 각각의 묶음 내의 수들을 내림차순으로 정렬한다.

 

 

 

 

M묶음으로 나누는 이유는 각각의 묶음에서 숫자 하나씩 선택을 하면 M개의 증가하는 수열을 만들 수 있다.

아래 그림에서 묶음1에서는 4를, 묶음2에서는 7, 묶음3에서는 8, 묶음4에서는 11, 묶음5에서는 13을 선택한다고 했을 때, 4 7 8 11 13 은 증가하는 수열이며 길이는 M이 된다.

 

 

 

또한 한 묶음안에는 최대 K개만큼의 수만 들어있으며, 하나의 묶음 내에서는 내림차순 정렬이기 때문에,

전체 수열에서 가장 긴 감소하는 수열의 길이는 K개가 된다. 

 

 

 

그렇다면 조건을 만족하지 못해서 -1 을 출력해야하는 경우는 언제일까?

 

<1>

만약에 M개의 묶음이 있고, 모든 묶음의 수의 개수가 K개이면 전체 수열의 길이는 M*K 이다.

이때가 최대이다. 왜냐하면 하나의 묶음에는 K개보다 많은 수가 들어있을 수 없기 때문이다.

그래서 만약에 전체 수열의 길이인 N이 M*K보다 크다면, 문제의 조건을 만족시킬 수 없다.

N > M*K 인 경우

 

<2>

M이 1일 때는 가장 긴 증가하는 수열의 길이가 1이란 뜻이므로 결국 내림차순으로 정렬된 상태이다.

그렇다면 이 때의 K는 N이 된다. -> M = 1, K = N

마찬가지로 K가 1일 때는 가장 긴 감소하는 수열의 길이가 1이란 뜻이므로 전체 수가 오름차순으로 정렬된 상태이다. 그렇다면 이 때의 M은 N이 된다. -> M = N, K = 1

즉, M + K 가 N + 1일 때가 최소이며, 만약에 M + K가 N + 1보다 크다면 문제의 조건을 만족시킬 수 없다.

M + K -1 > N 인 경우

 

 

전체 수열을 M개의 묶음으로 나누는 방법

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

 

한 묶음당 K이하의 수가 들어있으면서 M - 1 개수만큼의 묶음을 어떻게 만들까?즉, 나머지 수열 전체에서 구분선을 어디에 두어서 여러 개의 묶음으로 쪼갤 수 있을까?

 

N - K 길이의 수열을 M - 1 묶음으로 무조건 나눠야 하므로, N - K 를 M - 1 로 나누어서 한 묶음당 몇 개의 수가 들어가는지 확인한다. -> (N - K) / (M - 1)

그리고 나머지가 존재하면, 묶음당 하나씩 나머지를 배분한다.

 

 

예를 들어, 문제에서 주어진 조건이 N = 13, M = 5, K = 4 일 때, 처음 K개만큼의 수를 하나의 묶음으로 확보하고 남은 수열의 길이는 N - K = 13 - 4 = 9이고, 더 필요한 묶음은 M - 1 = 5 - 1 = 4개인 상황이다.

 

 

5 6 7 8 9 10 11 12 13 을 4개의 묶음으로 나누려면 하나의 묶음당 적어도 들어가는 수의 개수는?

9/4 = 2개이다. 그리고 나머지가 1개 존재한다.

이 나머지는 한 묶음당 하나씩 배분 완료할 때까지 추가해주면 된다.

(이 예시에서는 나머지가 한 개뿐이므로 하나의 묶음에 넣어주면 끝이다.)

 

 

 

소스코드 :