17829 222-풀링

 

 

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

17829번: 222-풀링

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	
	
	
	public static void main(String[] args) throws IOException {
	
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int 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());
			}
		}
		int answer=0;
		answer = second(matrix, N);
		System.out.println(answer);
		
	}
	
		public static int second(int matrix [][] , int N) {
	
	    Queue<Integer> result = new LinkedList<>();
		int small [] = new int [4];
		
		for(int i=0;i<N;i+=2) {
			for(int j=0; j<N;j+=2) {
				int index = 0;
			small[index++] = matrix[i][j];
			small[index++] = matrix[i][j+1];
			small[index++] = matrix[i+1][j];
			small[index++] = matrix[i+1][j+1];
			
			Arrays.sort(small);
			result.add(small[2]);
			}
		}
		
	
		N=N/2;
		matrix = new int [N][N];
		
		for(int i=0;i<N;i++) {
			for(int j=0; j<N;j++) {
				matrix[i][j] = result.poll();
			}
		}
		
		if(matrix.length==1) {
			return matrix[0][0];
		}else {
			return second(matrix, N);
                       // matrix.length가 1이 아니면 1이 나올 때까지 재귀
		}
		}
		}

 

분할정복을 잘 몰라서 아래 참고자료 블로그를 참고했다.

문제 예제 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

 

N=8

초기 Matrix는 

 

-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

 

이렇게 값이 들어온다.

 

그러면 2x2 정사각형에서 2번쨰로 큰 값을 고려하면 되므로 

처음에는 

-1 2 

10 6 

에서 2번째로 작은 큰 6

 

두 번째는

14 7

23 2 

에서 2번째로 큰 값인 14 ..

이렇게 고려해가면 된다.

 

그러면 위 작업을 small이라는 배열과 result라는 큐를 이용하는데,

i=0 j=0 일때

small[0] = -1

small[1] = 2

small[2] = 10

small[3] = 6

 

이렇게 값이 들어오고, 이 중에서 2번째로 큰 값인 6을

result 큐에다가 넣는다.

 

..

 

이렇게 하다보면 for문을 돌고나면 result큐에는

6 14 -1 9 9 5 20 6 8 4 5 8 17 19 21 23

이 값들이 들어오고,

얘네를 또 matrix크기를 반으로 줄여서(8->4)

matrix에 다시 넣어서

for문을 계속 돌리면 된다.

 

그러다가 matrix 크기가 1이 되면 그 값이 찾고자 하는 값이므로 출력하면 된다.  

 

 

 

 

참고 자료 : 

https://velog.io/@humblechoi/%EB%B0%B1%EC%A4%80-17829.-222-%ED%92%80%EB%A7%81-%EC%8B%A4%EB%B2%842

[백준] 17829. 222-풀링 (실버2)