[백준] 1201 NMK Python

문제 링크

1. 문제 설명

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

2. 문제 접근

아이디어는 간단합니다. 주어진 수 1부터 N을 순서대로 M개의 집합으로 나눕니다. M개의 집합 내부를 내림차순 정렬한 뒤 이어 붙입니다. 각 집합의 원소의 개수는 최대 k개이며, 최소한 하나의 집합은 k개의 원소를 가지고 있어야 합니다.

이 수열의 가장 긴 증가하는 부분 수열의 길이는 M입니다. 각 집합은 부분적으로 감소수열이기 때문에 각 집합에서 최대 한 개의 원소만 부분 수열에 포함할 수 있습니다. 가장 긴 감소하는 부분 수열의 길이도 K입니다. 한 집합의 모든 원소를 전부 다 포함하면 다른 집합의 원소를 포함할 수 없습니다. 각 집합은 오름차순 정렬되어 있으니까요.

N = 10, M = 4, K = 3일 때를 생각해 봅시다. 4개의 집합에 최대 3개의 숫자를 넣을 수 있으므로, 집합 1,2,3의 크기는 3, 4의 크기는 1입니다. 1부터 10까지 숫자를 차례대로 앞의 집합에 넣어 줍니다.

$1 : [1,2,3] \;, 2 : [4,5,6] \;, 3 : [7,8,9] \;, 4 : [10]$

이후 집합마다 뒤집어서 붙여주면 :

$[3,2,1 / 6,5,4 / 9,8,7/ 10]$

정답 수열을 구할 수 있습니다.

숫자 N개를 크기 K인 M개 집합에 넣는 문제이므로 예외 케이스가 발생합니다. N이 M * K보다 커서 숫자를 모두 집어 넣을 수 없거나, N개의 숫자가 충분치 않아서 첫 번째 집합에 K개의 원소가 있고 나머지 원소의 크기가 1인 최소 개수 $(M + (K - 1))$보다 모자르는 경우입니다. 이 두 가지 경우 예외 처리를 해줘야 합니다.

3. 문제 풀이

n, m, k = map(int, input().split())

if (n + 1 < m + k) or (n > m * k):
    print(-1)
    exit()

arr = [1] * m
if k == 1:
    print(*[i for i in range(1, m + 1)])
    exit()
    
d, r = (n - m) // (k-1) , (n - m) % (k-1)
for i in range(d):
    arr[i] = k
if r > 0 :
    arr[d] += r

ans = []
temp = 0
for a in arr:
    for i in range(temp + a, temp, -1):
        ans.append(i)
    temp += a

print(*ans)