222-풀링

면접 대비

시간 제한1초메모리 제한256 MB

요약
N×N 행렬의 각 2×2 블록을 두 번째로 큰 값으로 바꾸는 과정을 크기가 1×1이 될 때까지 반복하고 남는 수를 출력한다.
난이도

보통10점 중 4점

유형
구현, 시뮬레이션, 분할 정복, 정렬
정답자
아직 제출이 없습니다

문제

조기 졸업을 꿈꾸는 종욱이는 요즘 유행하는 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에서 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다.

다음은 8×8 행렬이 주어졌을 때 222-풀링을 1회 적용하는 과정이다.

  1. 행렬을 2×2 정사각형으로 나눈다.

  2. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1이라 했을 때 원소 a2를 뜻한다.

  3. 2번 과정에 의해 행렬의 크기가 줄어든다.

종욱이는 N×N 행렬에 222-풀링을 반복해서 적용해 크기를 1×1로 만들었을 때 어떤 값이 남는지 궁금해한다.

랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.

입력

첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)

다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다.

출력

마지막에 남은 수를 출력한다.

힌트

예제2는 본문에 이어 다음과 같은 과정으로 답을 구할 수 있다.

예제2

  1. 예제 1

    입력
    4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4
    예상 출력
    11

  2. 예제 2

    입력
    8
-1 2 14 7 4 -5 8 9
10 6 23 2 -1 -1 7 11
9 3 5 -2 4 4 6 6
7 15 0 8 21 20 6 6
19 8 12 -8 4 5 2 9
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
    예상 출력
    17