백준 1201 파이썬 NMK

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

1201번: NMK

 

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

if n < m+k-1 or n > m*k:
    print(-1)
else:
    l = list(range(k,0,-1))
    n -= k
    m -= 1
    while m:
        l.extend(range(k+n//m,k,-1))
        k += n//m
        n -= n//m
        m -= 1
    print(*l)

m+k-1 <= n <= m*k

 

1.  m+k-1 <= n

예를들어 m=2, k=2라고 했을 때
이 조건을 만족하는 가장 짧은 길이의 수열은 [1,3,2] 으로, n=3입니다.
여기서 LIS와 LDS가 공통적으로 3을 공유하고 있습니다.
이렇듯 가장 짧은 수열은 공통의 수 하나를 LIS와 LDS가 무조건 공유합니다.
따라서 n은 m+k-1보다 같거나 커야합니다.

 

 

2. n <= m*k

예를들어 m=2, k=2 라고 했을 때
이 조건을 만족하는 가장 긴 수열은 [ [2,1], [4,3] ] 으로, n=4입니다.
만약 n=5라면, 절대 만들 수 없습니다.

 

 

n=13, m=5 , k=4일때로 예를 들어보겠습니다.
A = [ [4,3,2,1], [6,5], [8,7], [10,9] ,[13,12,11] ]는 조건을 만족합니다.
여기서 LIS의 길이는 행의 개수입니다..(=5)
여기서 LDS의 길이는 열의 최대 길이입니다.(=4)

A = []로 두고, 먼저 k=4이므로 4,3,2,1 을 A에 추가합니다.
그 후 n개의 수 중에서 k개를 사용했으므로, n에서 k를 뺀다(n=9). 9개의 수를 앞으로 사용할 수 있습니다.
총 행의개수 5에서 행을 이미 하나 만들었으므로 앞으로 만들 행의 개수는 4개입니다.(m=4)
이제 앞으로 n과 m을 0으로 만들면 됩니다.

n//m = 9//4 = 2 다음으로 만들 행의 원소의 개수를 의미합니다.
[k+2:k] 의 수를 A에 추가합니다. 6,5가 추가됩니다.
2개의 수를 사용했기 때문에 n=7이고, 1개의 행을 더 만들었기 때문에 m=3이 됩니다.
k는 +=2를 해줘서 6으로 갱신해줍니다.
7//3 = 2이므로 A에 [k+2:k]인 8,7이 추가됩니다. 그 후 n,m,k = 5,2,8이 됩니다.
5//2 = 2이므로 A에 10,9가 추가합니다. n,m,k = 3,1,10
3//1 = 3이므로 A에 13,12,11이 추가합니다. n,m,k = 0,0,13
그럼 조건을 만족하는 수열이 완성됩니다.

 

 

만약 n=9 , m=3 , k=3이라면
A = []
A에 3,2,1 추가 n,m,k = 6,2,3
A에 6,5,4 추가 n,m,k = 3,1,6
A에 9,8,7 추가 n,m,k = 0,0,9

 

만약 n이 m*k보다 크다면, 길이가 m+1인 LIS나 k+1인 LDS가 무조건 만들어지기 때문에, 답을 구할 수 없습니다.