[python] 백준 24460 - 특별상이라도 받고 싶어

출처 : 백준, https://www.acmicpc.net/problem/24460

24460번: 특별상이라도 받고 싶어

 

룸메의 코골이를 피해 자취방으로 도피.......

덕분에 1일 1커밋 끊김.........다시 시작해야지 어휴

 

 

풀이

 

def Recursive(arr, start, end):
  start_x, start_y = start
  end_x, end_y = end
  
  if end_x - start_x == 1:
    return sorted([arr[start_x][start_y], arr[start_x][end_y], arr[end_x][start_y], arr[end_x][end_y]])[1]

  mid_x = int((start_x + end_x) // 2) + 1
  mid_y = int((start_y + end_y) // 2) + 1

  return sorted([Recursive(arr, (start_x, start_y), (mid_x-1, mid_y-1)), Recursive(arr, (start_x, mid_y), (mid_x - 1, end_y)), Recursive(arr, (mid_x, start_y), (end_x, mid_y-1)), Recursive(arr, (mid_x, mid_y), (end_x, end_y))])[1]

if __name__ == '__main__':
  n = int(input())
  arr = []
  
  for _ in range(n):
    arr.append(list(map(int, input().split())))

  if len(arr) == 1:
    print(arr[0][0])
  else:
    print(Recursive(arr, (0, 0), (len(arr)-1, len(arr)-1)))

 

일단 전부 살펴보지 않는 이상 답을 낼 수 없다고 생각해서 전부 살펴보도록 코드를 짜야겠다고 생각했다.

그런데 4등분해서 2번째를 찾는 패턴이 계속 반복되므로 재귀적으로 4등분하다가

2x2가 나오면 정렬해서 두 번째 값을 return하면 되겠다는 생각을 하였고, 이를 코드로 짰다.

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

재귀는 열심히 분석한 보람이 있네.