[BOJ] 17829. 222-폴링 (divide_and_conquer, implementation, recursion)

Silver II

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

17829번: 222-풀링

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

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

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

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

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

 

input:

• 첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)
• 다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다.

output:

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

 

---

Idea :

• 분할정복, 재귀 문제
  • 행렬을 4 구역으로 나누어 각각의 구역에서 위 규칙에 따라 마지막에 남은 수를 구한다
  • 그렇게 구한 4개의 숫자 중 두 번째로 큰 수가 답이 된다.
  • 4등분 된 각 구역의 마자막 남은 수를 구할 때에도 위 두 동작을 실행한다

Code :   

#include <iostream>
#include <queue>

using namespace std;

/* solve: (r,c) 부터 N * N 크기 행렬에 대해 222-폴링을 적용시키는 함수
 * 		  4구역으로 나누어 각각의 구역에 222-폴링을 적용시켜 얻어낸 4개의 숫자 중 두 번째로 큰 수
 * 
 * parameters - matrix: input으로 주어진 행렬
 *            - N: 222-폴링을 적용시킬 행렬의 범위/크기
 *            - r,c: 222-폴링을 적용시킬 행렬의 시작 좌표
 * return - (r,c) 부터 N * N 크기 행렬에 222-폴링을 적용시킨 결과
 */
int solve(int **matrix, int N, int r, int c) {
	if (N == 1) 
		return matrix[r][c];

	priority_queue<int> PQ;

	PQ.push(solve(matrix, N/2, r, c));
	PQ.push(solve(matrix, N/2, r + N/2, c));
	PQ.push(solve(matrix, N/2, r, c + N/2));
	PQ.push(solve(matrix, N/2, r + N/2, c + N/2));

	PQ.pop();
	return (PQ.top());
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	/* input & init */
	int N;
	cin >> N;

	int **matrix = new int*[N];
	for (int i=0; i<N; i++) {
		matrix[i] = new int[N]{};
		for (int j=0; j<N; j++)
			cin >> matrix[i][j];
	}

	/* solve */
	cout << solve(matrix, N, 0, 0) << "\n";

	/* free memory */
	for (int i=0; i<N; i++)
		delete[] matrix[i];
	delete[] matrix;

	return 0;
}

 

---

Result : 

메모리: 6248 KB, 시간: 148 ms

 

Review :

• 분할정복은 큰 문제를 작고 단순한 문제로 나누어 해결한 후 그 결과를 합치는 것
• 나눈 작은 문제가 해결됐다고 가정하고 문제 해결 방법을 찾아보기