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

 

17829번: 222-풀링

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

www.acmicpc.net

코드설명

분할정복 문제입니다.

 

문제로직입니다.

1. 0, 0에서 N 을 가지고서 분할정복 재귀가 실행됩니다.

2. map[N][N] 을 -> 4가지 로 나누어서 각 4분면에 해당하는 값들의 2x2가 될떄까지 재귀가 실행됩니다.

3. 마지막에는 결국 각 구간들의 2번쨰로 큰 수가 함수 첫 실행으로 돌아오게 되고 해당값의 arr[2]가 정답이 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M;
	public static int[][] map;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new int[N][N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	System.out.println(divideConquer(0, 0, N));
    }
	
	public static int divideConquer(int r, int c, int size) {
 
		if(size == 2) {
			int[] arr = new int[4];
			int idx = 0;
			for(int i=r; i<r+2;i++) {
				for(int j=c; j<c+2;j++) {
					arr[idx++] = map[i][j];
				}
			}
			Arrays.sort(arr);
			return arr[2];
		}else {
			int[] arr = new int[4];
			int nSize = size/2;
			
			arr[0] = divideConquer(r, c, nSize);
			arr[1] = divideConquer(r , c + nSize, nSize);
			arr[2] = divideConquer(r + nSize, c, nSize);
			arr[3] = divideConquer(r + nSize, c + nSize, nSize);
			
			Arrays.sort(arr);
			return arr[2];
		}
		
	}
	
 
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] Z 1074 - 분할정복 JAVA  (0) 2023.10.03
[백준] 쿼드트리 1992 - 분할정복(DivideAndConquer) JAVA  (0) 2023.10.02
[백준] 2630 색종이 만들기 - 분할정복 JAVA  (0) 2023.09.30
[백준] 9996 한국이 그리울 땐 서버에 접속하지 - 문자열(String) + 정규표현식(Regular Expression) + 동적계획법(DP, Dynamic Programming) JAVA  (0) 2023.09.28
[백준] 6987 월드컵 - 브루트포스(BruteForce) + 조합(Combination) JAVA  (0) 2023.09.27

+ Recent posts

티스토리툴바