백준 Silver 3 222-풀링

222-풀링 (백준 Silver 3)

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

분할 정복 알고리즘 중
쿼드트리를 기반으로 하는 알고리즘이다

분할 정복은
문제를 ‘작은 문제’로 쪼갠 후
그 해답을 모아 원래 문제를 풀어내는 방식이다

(DP와 다른점은
DP는 다른 선택지의 결과값을
새로운 선택지에서도 비교할 수 있지만
분할 정복은 그럴 수 없다는 점이다)

풀이 방식

쿼드트리는 ‘문제’를 ‘공통적인 방법’으로 풀되
그 ‘범위’를 4분할 하여 나가는 방식이다

따라서 코드를 정리하자면

• 시작 위치(start y,x)를 지정
  
• n을 분할하여, recur이 서로 다른 범위를 탐색하도록 한다
  
• recur의 종료조건(n==1)을 지정
  
• 4개의 값을 모아 2번째로 큰 값을 반환
  

결과

제출 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int recur(vector<vector<int>>& vec, int n, int startY, int startX)
{
	if (n == 1)
	{
		return vec[startY][startX];
	}

	vector<int> p;
	p.push_back(recur(vec, n / 2, startY, startX));
	p.push_back(recur(vec, n / 2, startY + n / 2, startX));
	p.push_back(recur(vec, n / 2, startY, startX + n / 2));
	p.push_back(recur(vec, n / 2, startY + n / 2, startX + n / 2));

	sort(p.begin(), p.end());
	
	return p[2];
}

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> vec(n, vector<int>(n, 0));

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> vec[i][j];

	cout << recur(vec, n, 0, 0);
}