[백준][Python]1201번(NMK)

백준 1201번

최종 제출 코드

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

def make_arr(arr):
    answer = []
    for i in range(len(arr)):
        for j in range(len(arr[i])):
            answer.append(arr[i][j])
    return answer
  
def solution(n, m, k):
  if m+k>n+1: return
      
  arr = []

  if m>=k:
      for i in range(n+1-m, -m, -m):
          arr.append([j for j in range(i, i+m) if j>0])
      down = math.ceil(n/m)
      if down == k: return make_arr(arr)
      elif down>k: return
      else:
          target = k-down+1
          if len(arr[1])>=target:
              arr[1][:target] = sorted(arr[1][:target],reverse=True)
              return make_arr(arr)
          return

  else:
      for i in range(1, n+1, k):
          arr.append([j for j in range(k+i-1, i-1, -1) if j<=n])
      
      up = math.ceil(n/k)
      if up == m: return make_arr(arr)
      elif up > m: return
      else:
          target = m-up+1
          if len(arr[-1])>=target:
              arr[-1][:target] = sorted(arr[-1][:target])
              return make_arr(arr)
          return

answer = solution(n, m, k)

if answer:print(*answer)
else: print(-1)

◾ 그리디 알고리즘..?

• 유일하게 알고리즘 분류의 기준을 이해할 수 없는게 그리디 알고리즘인것 같다...
  (이게 왜 그리디..? 그리디가 정확히 뭔데..?)

◾ 풀이

• 처음엔 실패할걸 알면서도 dfs로 풀이했다. 그런데 역시나 테스트케이스만 돌려보는데도 실행시간이 너무 길게 걸렸다. 코드를 제출하면 100% 시간초과가 뜰거라고 확신.
• 다른 풀이를 생각해보자!
• if m>=k 부분의 코드를 그림으로 표현하면 아래와 같다
  
• n = 15, m = 5, k = 4라고 가정하자.
• 이 경우엔 내림차순으로 m(=5)개씩 끊어 배열을 생성한다. (이때 배열은 오름차순 정렬)
• 이렇게 생성하는 이유는 하나의 행 안에서는 오른쪽으로 이동할때 무조건 수가 증가하고, 행을 벗어나 다른 열로 이동하는 경우는 수가 감소하게 만들기 위해서다.
  ▶️ 큰수부터 5개씩 끊어 오름차순으로 정렬된 배열을 생성했기 때문에 증가하는 수열의 길이는 5개를 초과할 수 없다.
  ▶️ 만약 작은수부터 5개씩 끊어 오름차순으로 정렬된 배열을 생성했다면 이때는 증가하는 수열의 길이가 n개가 된다!!!!! (ex. 1 2 3 4 5 / 6 7 8 9 10 / 11 12 13 14 15)
• 수열을 잘 살펴보자!
  ▶️ 11(1행의 첫번째 원소)보다 작은수는 15(1행의 마지막 원소)의 뒤에만 있다
  ▶️ 6(2행의 첫번째 원소)보다 작은수는 10(2행의 마지막 원소)의 뒤에만 있다
  ▶️ 1(마지막행의 첫번째 원소)보다 작은수는 없다!
• 증가하는 수열의 길이가 m개를 초과할 수 없는 이유이다
• 이렇게 배열의 생성을 마쳤을때, 감소하는 수열의 길이가 행의 개수보다 적다면 이 경우는 생성이 불가능하다.
• 그림을 살펴보자. 위에서 아래로 이동하는 경우는 무조건 수가 감소한다.
  (어떤 케이스를 검사해봐도 행이 증가하는 경우에는 무조건 수가 감소한다.)
• 수열이 3개의 그룹으로 나뉘었기 때문에 감소하는 수열의 길이는 적어도 3이어야 한다.
• k < math.ceil(n/m)인 경우는 수열 생성이 불가능한 케이스다. None을 반환한다.
• k == math.ceil(n/m)인 경우, 이미 k개만큼의 감소하는 수열이 생성되어 있다.
• k > math.ceil(n/m)인 경우, 이미 math.ceil(n/m) 길이의 감소하는 배열은 생성되어 있다.
  ▶️ 수열의 길이를 1 증가시켜야 하면, 오름차순 정렬된 두개의 숫자의 자리를 바꿔줘야한다.
  ▶️ 수열의 길이를 2 증가시켜야 하면, 오름차순 정렬된 세개의 숫자의 자리를 바꿔줘야한다.
  ▶️ target = k - math.ceil(n/m) + 1
• 감소하는 수열의 길이를 늘이기 위해 숫자를 바꿔줄 행을 선택해야한다.
• 첫번째 행은 무조건 제외하고, 두번째 행을 대상으로 삼는다.
  ▶️ 증가하는 수열의 길이를 지키기 위함이다.
  ▶️ 두번째 행이 첫번째 행 바로 다음에 생성된 배열이기 때문에, 이후의 배열들의 길이보다 무조건 같거나 길다.
  ▶️ 이때 두번째 행의 길이가 target보다 작다면 감소하는 수열의 길이를 만족시킬 수 없다. None을 반환한다.
  ▶️ target보다 크거나 같다면, 배열내의 원소를 target개수만큼 내림차순 정렬한다.
• m < k의 경우도 같은 논리를 적용시켜 약간의 수정만 해주면 된다.
• k가 더 큰 경우는 감소하는 수열을 먼저 확보하고 시작해야 하기 때문에 오름차순으로 k개씩 끊어, 행 내의 원소가 내림차순된 배열을 생성한다.
• 마지막에도 필요한 증가하는 수열의 target만큼 오름차순 정렬로 변경하면 된다.

◾ 소감

• 플래티넘 문제는 처음 풀어 보는데 심지어 플래티넘 3이다...! 우왕