[백준 17829] 222-풀링 (C++)

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

문제

---

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

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

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

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

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

입력

---

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

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

 

출력

---

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

 

문제 풀이

---

재귀 문제.

 

행렬의 크기가 1이 될 때까지 반복해서 행렬을 2*2 정사각형으로 나누어 두 번째로 큰 값만을 뽑아내어 새 행렬을 만든다. 따라서 재귀함수를 이용한다.

설명한대로 그대로 구현해주면 된다. 크기가 1이라면 행렬에 들어있는 그 요소를 반환하면 되고, 그 이외에는 현재 행렬의 길이의 1/2이 되는 새 행렬을 만들어 현재 행렬의 2*2 정사각형 중 두번째로 큰 요소를 새 행렬에 넣는다. 4개짜리 배열을 만들어 오름차 순 정렬한 후 3번째 요소를 반환하면 쉽게 두번째로 큰 요소를 구할 수 있다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

int pooling(int** arr, int length)
{
	if (length == 1)
	{
		return arr[0][0];
	}
	else
	{
		int newLength = length / 2;
		int** newArr = new int*[length / 2];
		for (int i = 0; i < newLength; i++)
		{
			newArr[i] = new int[newLength];
		}
		for (int i = 0; i < length; i+=2)
		{
			for (int j = 0; j < length; j += 2)
			{
				int part[] = {arr[i][j], arr[i + 1][j], arr[i][j + 1], arr[i + 1][j + 1]};
				sort(part, part + 4);
				newArr[i / 2][j / 2] = part[2];
			}
		}
		return pooling(newArr, newLength);
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int** arr = new int*[N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[N];
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
		}
	}
	cout<<pooling(arr, N);
	return 0;
}