[C/C++] 백준 - 17829번 (222 - 폴링)

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

17829번: 222-풀링

문제

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

다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다

1. 행렬을 2×2 정사각형으로 나눈다.
2. 
3. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다.
4. 
5. 2번 과정에 의해 행렬의 크기가 줄어들게 된다.

종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다.

랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.

입력

첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)

다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다. 

출력

마지막에 남은 수를 출력한다.

 

분할정복을 이용하는 문제이다.

주어진 행렬을 2x2로 나눈 후 그 안에서 2번째로 큰 수만 뽑아 뽑은 수로만 다시 행렬의 형태를 이룬다

이 과정을 반복한 후 1개의 수만 남았을 때의 수를 출력하는 문제이다

 

하라는 대로 처음에 입력한 N을 2로 나눈 후, 

이중for문을 이용해 분할을 해야하는 각 구역을 정해준다.

그 정해준 구역 내 모든 수를 vector에 넣어주고, vector를 정렬해주면 2번째 value가 2번째로 큰 값이 된다.

그것만 큐에 넣어주면 각 범위에서 2번째로 큰 값만 들어가고, 분할을 이용한 각 범위 탐색이 끝났으면

다시 행렬의 값들을 큐에 들어가있는 값으로만 초기화 시켜주는 것이다.

그리고 N을 2로 나누었을 때의 값이 1이 된다면 큐에 들어가있는 값을 빼서 다시 행렬로 만드는 과정은 생략하고

바로 반복문을 빠져나와 큐에 들어가있는 하나의 값을 출력하면 답이 되는것이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<algorithm>
#define MAX_SIZE 1025
#define swap(type,x,y) do{type t=x;x=y;y=t;} while(0)

using namespace std;

int N, remember_N;
int falling[MAX_SIZE][MAX_SIZE];
queue<int> q;

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0;  j < N; j++) {
			cin >> falling[i][j];
		}
	}
	remember_N = N;
}

bool compare(int a, int b) {
	if (a > b) return true;
	else return false;
}

void func(int x, int y) {
	vector<int> v;
	for (int i = x; i < x + 2; i++) {
		for (int j = y; j < y + 2; j++) {
			v.push_back(falling[i][j]);
		}
	}
	sort(v.begin(), v.end(),compare);
	q.push(v.at(1));
	v.clear();
}

void Falling_Down(int size, int x, int y) {
	int n = size / 2;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			func(x + i * 2, y + j * 2);
		}
	}
	remember_N = n;
}

int main() {
	input();
	while (1) {
		Falling_Down(N, 0, 0);
		if (remember_N == 1) break;
		for (int i = 0; i < N / 2; i++) {
			for (int j = 0; j < N / 2; j++) {
				int data = q.front();
				q.pop();
				falling[i][j] = data;
			}
		}
		N = N / 2;
	}

	cout << q.front();
	return 0;
}