[Silver II] 222-풀링 - 17829

문제 링크

성능 요약

메모리: 101716 KB, 시간: 716 ms

분류

분할 정복, 구현, 재귀

제출 일자

2024년 2월 4일 04:34:06

문제 설명

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

다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다

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

   <p><img alt="" src="https://upload.acmicpc.net/61c48878-d2bb-4680-a7d3-8f9922f3c30f/-/preview/" style="width: 350px; height: 350px;"></p>
   </li>
   <li>
   <p>각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a<sub>4 </sub>≤<sub> </sub>a<sub>3 </sub>≤ a<sub>2 </sub>≤<sub> </sub>a<sub>1</sub> 라 했을 때, 원소 a<sub>2</sub>를 뜻한다.</p>
   
   <p><img alt="" src="https://upload.acmicpc.net/c2d98fd8-f0dd-4ab4-8fe7-f360e74fa86e/-/preview/" style="height: 350px; width: 676px;"></p>
   </li>
   <li>
   <p>2번 과정에 의해 행렬의 크기가 줄어들게 된다.</p>
   </li>

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

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

입력

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

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

출력

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

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int[][] matrix;
	public static void main(String[] args) throws IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		matrix=new int[n][n];
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		System.out.println(recur(0,0,n));

	}
	public static int recur(int i,int j, int size) {
		if(size==2) {
			int[] arr = new int[4];
			int idx=0;
			for(int r=i;r<i+2; r++) {
				for(int c=j; c<j+2; c++) {
					arr[idx++]=matrix[r][c];
				}
			}
			Arrays.sort(arr);
			return arr[2];
		}
		else {
			int[] arr = new int[4];
			size/=2;
			arr[0]=recur(i,j,size);
			arr[1]=recur(i,j+size,size);
			arr[2]=recur(i+size,j,size);
			arr[3]=recur(i+size,j+size,size);

			Arrays.sort(arr);
			return arr[2];
		}
	}

}

[문제 풀이 + 코드 참고]
재귀에 조금 더 익숙해져야 함을 느낄 수 있다.
아직 재귀에 대해선 많이 약한 것 같다.