[백준/1201] NMK (Python)

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

1201번: NMK

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:53:51

 

---

 

문제 설명

 

 

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

4 2 2

 

출력 예시

 

2 1 4 3

 

 

---

 

풀이

 

우선 -1이 되는 조건부터 생각해 보자. 최소의 경우를 생각해 보면, 모든 수가 최장 증가 부분 수열 및 최장 감소 부분 수열에 관여하는 경우가 있겠다. 가령 (7, 4, 4)으로 주어졌다면, 4 5 6 7 3 2 1 와 같은 꼴이 된다. 즉 M + K은 N+1보다 작거나 같아야 한다.

두 번째로, 최대의 경우를 생각해 보자.  하나의 감소 부분 수열은 최대 길이가 K여야 하며, 이 부분 수열의 최댓값들이 최장 증가 부분 수열에 관여하는 형태를 생각하자. 가령 (9, 3, 3)으로 생각해 본다면, 3 2 1 6 5 4 9 8 7 와 같은 경우가 된다. 여기서 N이 1이라도 늘어나게 되면, 비둘기집의 원리에 의해 최장 증가 부분 수열 혹은 최장 감소 부분 수열의 값이 M, K라는 전제에 모순된다. 따라서 M*K은 N보다 크거나 같아야 한다.

 

 

-1을 구할 때 우리는 벌써 그리디한 하나의 해를 도출해 볼 수 있다. 하나의 감소 부분 수열은 최대 길이가 K여야 하며, 이 부분 수열의 최댓값들이 최장 증가 부분 수열에 관여하는 형태. 즉 (감소 수열) - (감소 수열) - (감소 수열) 형식으로 그리디하게 해를 구성할 수 있다. 이 때, 앞선 감소 수열의 모든 원소는 뒤의 감소 수열의 모든 원소보다 작음이 보장되어야 한다. 또한 총 감소 수열의 개수는 M개여야 하며, 하나 이상의 감소 수열의 길이가 K임이 보장되는 해를 출력하면 된다.

 

 

풀이 코드

N, M, K = map(int, input().split())

if M + K > N + 1 or M*K < N:
  print(-1)
  exit()
if M == 1 :
  print(*range(N, 0, -1))
  exit()
if K == 1 :
  print(*range(1, N+1))
  exit()

ans = list(range(K, 0, -1))
cur = K + 1
dec_len, left_dec = (N-K) // (M-1), (N-K) % (M-1)

while cur <= N :
  nxt = cur + dec_len - 1
  if left_dec :
    nxt += min(left_dec, K - dec_len)
    left_dec -= min(left_dec, K - dec_len)
  ans += list(range(nxt, cur-1, -1))
  cur = nxt+1
print(*ans)

풀이 완료!