Baekjoon Online Judge 17829번 파이썬. 분할정복.

문제링크

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

17829번: 222-풀링

 

'divide=size//2'로 정사각형을 4등분을 할 수 있도록 하였다.

그리고 dnc함수에서 lefttop,righttop,leftbottom,rightbottom으로 나누어 진행될 수 있도록 하였다.

 

정답코드

import sys

N = int(sys.stdin.readline())
nums = []
for i in range(N):
  nums.append(list(map(int,sys.stdin.readline().split())))
  
def dnc(size,x,y):
  divide = size // 2
  if size == 2:
    group=[nums[x][y], nums[x+1][y], nums[x][y+1], nums[x+1][y+1]]
    group.sort(reverse=True) #내림차순 정렬
    return group[1]

  lefttop = dnc(divide,x,y)
  righttop = dnc(divide,x+divide,y)
  leftbottom = dnc(divide,x,y+divide)
  rightbottom = dnc(divide,x+divide,y+divide)
  group = [lefttop,righttop,leftbottom,rightbottom]
  group.sort(reverse=True)
  return group[1]

print(dnc(N,0,0))