17829번: 222-풀링

222-풀링

 

시간 제한        메모리 제한        제출        정답        맞힌 사람        정답 비율

 

1 초

256 MB

2314

1678

1349

75.574%

문제

조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(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 복사

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

힌트

예제2는 본문에 이어 다음과 같은 과정으로 답을 구할 수 있다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, a[1026][1026], arr[4], s[1026][1026];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> a[i][j];
        }
    }
    //2. 풀링 만들기
    while(n!=1){
        for(int i=0;i<n-1;i+=2){
            for(int j=0;j<n-1;j+=2){
                arr[0]=a[i][j]; arr[1]=a[i][j+1];
                arr[2]=a[i+1][j]; arr[3]=a[i+1][j+1];
                sort(arr, arr+4);
                a[i/2][j/2]=arr[2];
            }
        }
        n/=2;
    }
    //3. 정답 출력
    cout << a[0][0];
}

 

폴링시 배열을 덮어쓰고 계속해서 조회 범위만 줄이면 원래 배열을 계속 사용할 수 있다.