[JAVA] 백준 1201번 NMK

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

1201번: NMK

이 문제는 nmk 공식에 맞는 수열을 만드는 로직을 생각하고,

풀면서 생각하지 못한 여러가지 예외가 많이 나와서 애먹었다.

먼저, m값(길이가 가장 긴 증가하는 부분 수열)과 k값(길이가 가장 긴 감소하는 부분 수열)에 따라서

가능한 n값의 범위가 있다. (13~16번 줄)

 

m 과 k 가 모두 3이라고 가정하면,

n이 최소로 될 수 있는 값은 {3, 2, 1, 4, 5} → 5값(m+k-1)을 가질 수 있고

n이 최대로 될 수 있는 값은 {3, 2, 1, 6, 5, 4, 9, 8, 7} → 9값(m*k)을 가질 수 있다.

n 안에서 증가하는 수열 m의 개수를 가지려면 m만큼의 수로 그룹을 나누고, 그 그룹 안에서 최대 k 값을 가질 수 있다.

그룹별로 봤을때는 증가하는 수열을 만들고, 그룹 안에서는 감소하는 수열을 만들 수 있기 때문이다.

 

나는 m과 k값을 이용하여 n값을 가진 수열을 만들 때, 아래와 같은 규칙을 사용했다.

[n = 12, m = 4, k = 3 인 경우]

먼저, 처음에는 감소하는 수열 k값을 나열한다. → {3, 2, 1}

다음은 m 값을 만들어야 한다. → { [(3, 2, 1), 4, 5, 6] } → ()괄호는 감소, [] 괄호는 증가

그런데, 위와같이 (3), 4, 5, 6으로 만들면 7~12의 수를 추가해야하는데 증가하는 수열이 계속 늘어나게 된다.

그래서 최대값이 n값이 되도록 k값 다음 m 값을 셋팅해준다. → {(3, 2, 1), 10, 11, 12}

 

이제 m값과 k값이 증가하지 않도록 남은 값을 추가해야 한다.

제일 첫 그룹에 가장 작은 수를 지정해줬으므로, 남은 수를 증가하도록 넣으면서 m과 k의 최대값을 초과하지 않도록 만든다.

→ {(3, 2, 1), [10, 11, 12] , [7, 8, 9] , [4, 5, 6]}

위와 같은 규칙으로 만들면 감소하는 수의 최대값은 k 또는 (n-k)/(m-1)이 된다.

(n-k)/(m-1) <= k   →    n - k <= m*k - k   →  n <= m*k 법칙이 성립한다.(13번 줄)

 

코드를 작성하면서 빼먹었던 예외사항은, (n-k)/(m-1)이 나머지 없이 나누어 떨어지지 않는 경우를 빼먹어서였다.

나머지는 증가하도록 넣어주고,

m이 1인 경우도 따로 계산해 주었다.

 

 

정석인 정답은 n을 m개의 그룹으로 나누고, 그룹중 최대값은 k값, 남은 나머지는 각 그룹에 하나씩 넣어주면서

그룹 안에서의 값은 감소하는 값, 그룹별로 보았을 때는 증가하는 값을 넣어주는 로직이었다.