이번 문제는 보자마자 분할 정복을 통해 해결해야겠다고 생각했다. 배열의 크기가 고정적이라면 하드코딩도 가능하겠지만 크기가 유동적이기 때문에 재귀함수를 통한 분할 정복 기법으로 해결하였다.

함수의 인자는 배열의 크기, x좌표, y좌표로 지정하였고 좌측 상단, 우측 상단, 좌측 하단, 우측 하단으로 나누어 모든 실행에서의 배열의 크기가 2가 될 때까지 나누고 그 중 두번째로 큰 수를 저장하는 방식으로 진행하였다.

코드의 구성은 다음과 같다.

• n을 입력받는다.
• 행렬을 받을 배열 nums를 선언한다.
• n번 반복하며 행렬을 입력받아 nums에 넣어준다.
• 222-풀링 연산을 처리하는 pooling 함수를 size, x, y를 인자로 넣어 선언한다. 이때 size는 행렬의 행 혹은 열의 크기이고, x, y는 x ,y좌표를 나타내기 위함이다.
  -> size를 2로 나눈 수를 mid변수에 저장한다.
  -> 만약 size가 2라면 answer배열에 nums[x][y], nums[x+1][y], nums[x][y+1], nums[x+1][y+1]을 넣어주고 answer을 오름차순으로 정렬한다. 그리고 answer[-2]를 반환해준다. (이 경우는 문제에서 주어진 행, 열이 2일 때에 그 중 두번째로 큰 수를 취하는 과정이다.)
  -> 좌측 상단 구역을 나타내는 변수 lt에 pooling 함수에 mid, x, y를 넣어 실행시킨다.
  -> 우측 상단 구역을 나타내는 변수 rt에 pooling 함수에 mid, x+1, y를 넣어 실행시킨다.
  -> 좌측 하단 구역을 나타내는 변수 lb에 pooling 함수에 mid, x, y+1을 넣어 실행시킨다.
  -> 우측 하단 구역을 나타내는 변수 rb에 pooling 함수에 mid, x+1, y+1을 넣어 실행시킨다.
  (이 과정을 재귀적으로 처리함으로써 2x2 행렬까지 나눠져 위에서 실행한 과정을 반복하도록 한다.)
  -> answer에 lt, rt, lb, rb를 넣어준다. (이 과정은 위에서 반복적으로 처리한 후 최종으로 가져오는 값들을 answer에 저장하는 과정이다.)
  -> answer를 오름차순 정렬한다.
  -> answer[-2]를 반환한다.
• pooling(n, 0, 0)의 결과를 출력한다.

Code

n=int(input())
nums=[]
for i in range(n):
    tmp=list(map(int, input().split()))
    nums.append(tmp)
def pooling(size, x, y):
    mid=size//2
    if size==2:
        answer=[nums[x][y], nums[x+1][y], nums[x][y+1], nums[x+1][y+1]]
        answer.sort()
        return answer[-2]
    lt=pooling(mid, x, y)
    rt=pooling(mid, x+mid, y)
    lb=pooling(mid, x, y+mid)
    rb=pooling(mid, x+mid, y+mid)
    answer=[lt, rt, lb, rb]
    answer.sort()
    return answer[-2]
print(pooling(n, 0, 0))