[python] 백준 1201 NMK

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

1201번: NMK

 

문제 해결

• 먼저 수열을 구할 수 있기 위한 n의 범위를 알아야한다.
  • m+k-1 ≤ n ≤ m*k 이다.
    • n이 가장 작을 때는 [1, 2, 3, .. . m, m-1, m-2, . . . m+k-1] 수열이며
    • n이 가장 클 때는 [k,k-1,k-2, . . . 1, 2*k, 2*k-1, . . . k+1, . . . m*k, m*k-1, . . . (m-1)*k + 1] 이다.
• n이 범위 안에 들어오면 처음으로 k개의 숫자를 내림차순해서 k개의 내림차순을 만든다.
• 이제 k+1~n까지 정렬해서 m-1개의 오름차순 수열을 만들어야한다.
• 여기서부터 너무 어려워서 찾아보게 되었다.
  
  • m개의 내림차순 그룹을 만들 때 처음 1그룹에 k개의 내림차순 수열을 만들었으므로
  • n -= k, m-=1 을 한다.
  • m이 0이 될때까지
    • 다음 그룹에 n//m개의 원소를 내림차순으로 넣고
    • n 을 n//m 만큼 빼주고
    • m -= 1 씩 빼주면서 그룹을 만들어 나간다.

CODE

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


if m+k-1<=n<=m*k:
    arr = [i for i in range(k,0,-1)]
    n -= k
    m -= 1
    while m:
        arr.extend(range(k+n//m,k,-1))
        k += n//m
        n -= n//m
        m -= 1
    print(*arr)
else:
    print(-1)