[Silver II] 222-풀링 - 17829
성능 요약
메모리: 114204 KB, 시간: 552 ms
분류
분할 정복, 구현, 재귀
제출 일자
2024년 1월 12일 14:49:42
문제 설명
조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다.
다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다
종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다.
랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.
입력
첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)
다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다.
출력
마지막에 남은 수를 출력한다.
접근 방법
1. n / 2크기의 배열을 만들어준 뒤 값을 채워주는 메서드 -> n이 1이 될 때 까지
2. 각 배열을 쪼개어 n / 2 크기 배열에 값을 넣어주는 메서드
3. 주어진 범위내에 두번째로 큰 수를 찾는 메서드
1. n / 2 크기 배열을 만들어주는 메서드
// n 값이 1이 될 때 까지 recursion으로 만든다.
private static void recursion() {
// n == 1일 때 값을 출력하고 종료
if(n == 1) {
System.out.println(answer[0][0]);
return;
}
// n / 2 크기의 새로운 배열
answer = new int[n/2][n/2];
// answer 배열에 풀링을 적용함
recursionMake(0,0,n);
// 기존 배열에 n / 2 크기 배열을 넣어준 뒤 n / 2로 만든다.
map = answer;
n /= 2;
// 현재 실행중인 메서드를 재귀 호출한다.
recursion();
}
2. 각 배열을 쪼개어 n / 2 크기 배열에 값을 넣어주는 메서드
// 현재 배열을 범위로 나누어준다.
private static void recursionMake(int x,int y, int len) {
// 변이 2일 때 두번째로 큰 크기를 찾아서 배열에 넣어준다.
if(len == 2) {
searchSecondMax(x,y);
return;
}
len /= 2;
// 각 범위별로 재귀 호출
recursionMake(x,y,len);
recursionMake(x+len,y,len);
recursionMake(x,y+len,len);
recursionMake(x+len,y+len,len);
}
3. 주어진 범위내에 두번째로 큰 수를 찾는 메서드
// 두번째로 큰 값을 찾아준다.
private static void searchSecondMax(int x,int y) {
// 4개의 값을 배열로 만들어준 뒤 정렬 후 2번째로 큰 수를 찾아서 answer배열에 넣어준다.
int[] nums = new int[] {map[x][y], map[x][y+1],map[x+1][y], map[x+1][y+1]};
Arrays.sort(nums);
answer[x / 2][y/2] = nums[2];
}
전체 풀이 코드
import java.io.*;
import java.util.*;
class Main{
static int[][] map;
static int[][] answer;
static int n;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
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());
}
}
// 재귀
recursion();
}
// n 값이 1이 될 때 까지 recursion으로 만든다.
private static void recursion() {
// n == 1일 때 값을 출력하고 종료
if(n == 1) {
System.out.println(answer[0][0]);
return;
}
// n / 2 크기의 새로운 배열
answer = new int[n/2][n/2];
// answer 배열에 풀링을 적용함
recursionMake(0,0,n);
// 기존 배열에 n / 2 크기 배열을 넣어준 뒤 n / 2로 만든다.
map = answer;
n /= 2;
// 현재 실행중인 메서드를 재귀 호출한다.
recursion();
}
// 현재 배열을 범위로 나누어준다.
private static void recursionMake(int x,int y, int len) {
// 변이 2일 때 두번째로 큰 크기를 찾아서 배열에 넣어준다.
if(len == 2) {
searchSecondMax(x,y);
return;
}
len /= 2;
// 각 범위별로 재귀 호출
recursionMake(x,y,len);
recursionMake(x+len,y,len);
recursionMake(x,y+len,len);
recursionMake(x+len,y+len,len);
}
// 두번째로 큰 값을 찾아준다.
private static void searchSecondMax(int x,int y) {
// 4개의 값을 배열로 만들어준 뒤 정렬 후 2번째로 큰 수를 찾아서 answer배열에 넣어준다.
int[] nums = new int[] {map[x][y], map[x][y+1],map[x+1][y], map[x+1][y+1]};
Arrays.sort(nums);
answer[x / 2][y/2] = nums[2];
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 1935번 : 후위 표기식2 Silver3(실버3) - JAVA[자바] (1) | 2024.01.14 |
---|---|
[백준] 1991번 : 트리 순회 Silver1(실버1) - JAVA[자바] (1) | 2024.01.14 |
[백준] 11725번 : 트리의 부모 찾기 Silver2(실버2) - JAVA[자바] (1) | 2024.01.11 |
[백준] 18111번 : 마인크래프트 Silver2(실버2) - JAVA[자바] (0) | 2023.12.15 |
[백준] 1676번 : 팩토리얼 0의 개수 Silver5(실버5) - JAVA[자바] (0) | 2023.12.13 |