| 1 초 | 256 MB | 2019 | 1447 | 1157 | 74.501% |
문제
조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다.
다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다
- 행렬을 2×2 정사각형으로 나눈다.
- 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다.
- 2번 과정에 의해 행렬의 크기가 줄어들게 된다.
종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다.
랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.
입력
첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)
다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다.
출력
마지막에 남은 수를 출력한다.
예제 입력 1 복사
4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4
예제 출력 1 복사
11
예제 입력 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
예제 출력 2 복사
17
풀이
해당 문제는 재귀용법, 분할정복을 활용하여 풀이하면 된다.
마찬가지로 브레이크 포인트를 어디서 잡느냐가 중요하다.
해당 문제는 2X2 배열이 끝이고 그 배열에서 2번쨰로 가장 큰 수를 반환해야하기 때문에
배열의 크기가 N*N 즉 N=2 일때 반환하도록 하면 된다.
다른 문제들과 마찬가지로 상하좌우로 4등분 하는식으로 쪼개기 때문에
브레이크 포인트에서 크기가 4인 배열을 만들고 정렬 후 2번째로 큰 값 반환
그리고 각 파트별로 (상하좌우) 2번쨰로 큰 값을 구한 후 마지막으로 2번째로 큰 값을 구하는식으로 전개를 하면 된다.
if(N==2){
int count=0;
int[] funcArr= new int[4];
for(int i=row ; i<row+N;i++){
for(int j=col ; j<col+N; j++){
funcArr[count] = arr[i][j];
count++;
}
}
Arrays.sort(funcArr);
return funcArr[funcArr.length-2];
}브레이크 포인트를 이렇게 잡아준다.
public static int func(int row,int col,int N){
if(N==2){
int count=0;
int[] funcArr= new int[4];
for(int i=row ; i<row+N;i++){
for(int j=col ; j<col+N; j++){
funcArr[count] = arr[i][j];
count++;
}
}
Arrays.sort(funcArr);
return funcArr[funcArr.length-2];
}
N = N/2;
int[] funcArr = new int[4];
int count =0;
for(int i=0; i<2;i++){
for(int j=0; j<2;j++){
funcArr[count] = func(row+(i*N),col+(j*N),N);
count++;
}
}
Arrays.sort(funcArr);
return funcArr[funcArr.length-2];
}함수를 이렇게 호출해주면 된다 .
package baekjoon.a17829;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class a17829 {
public static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for(int i=0; i<N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(func(0,0,N));
}
public static int func(int row,int col,int N){
if(N==2){
int count=0;
int[] funcArr= new int[4];
for(int i=row ; i<row+N;i++){
for(int j=col ; j<col+N; j++){
funcArr[count] = arr[i][j];
count++;
}
}
Arrays.sort(funcArr);
return funcArr[funcArr.length-2];
}
N = N/2;
int[] funcArr = new int[4];
int count =0;
for(int i=0; i<2;i++){
for(int j=0; j<2;j++){
funcArr[count] = func(row+(i*N),col+(j*N),N);
count++;
}
}
Arrays.sort(funcArr);
return funcArr[funcArr.length-2];
}
}'Algorithm' 카테고리의 다른 글
| 백준 1003번 피보나치 함수 (자바) 풀이 (0) | 2022.12.28 |
|---|---|
| 백준 2447번 별 찍기 - 10 (자바) 풀이 (0) | 2022.12.26 |
| 백준 1780번 종이의 개수 (자바) 풀이 (0) | 2022.12.26 |
| 백준 2630번 색종이 만들기 (자바) 풀이 (0) | 2022.12.26 |
| 다이나믹 프로그래밍 / 분할정복 (을 활용한 병합정렬/퀵정렬) (0) | 2022.12.26 |