백준 24460번: 특별상이라도 받고 싶어 (C++)

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

24460번: 특별상이라도 받고 싶어

 

풀이

분할 정복 문제. 개념이 이해가 안되서 유형 부수기 중.

 

사실상 재귀 문제인데 어떻게 설계하는 지가 중요한 듯 하다.

4가지 의자 중에 2번째로 숫자가 작은 의자를 골라야해서 ans[4] 배열에 4가지 분할 된 함수의 값을 넣고

ans[1]을 리턴하면 재귀적으로 ans[4] 배열에는 2번째로 작은 의자만 담기게 된다.

 

사실 나도 잘 모르겠다. 재귀는 그냥 느껴야 하는 것 같다.

 

 

 

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

17829번: 222-풀링

근데 이 문제랑 똑같은 문제인데 왜 난이도가 다르냐

 

전체 코드

#include <iostream>
#include <cmath>
#include <set>
#include <algorithm>

using namespace std;

int N;
int chair[1100][1100] = { 0, };

int partition(int x, int y, int n) {
	int ans[4] = { 0, };
	if (n >= 2) {
		ans[0] = partition(x, y, n / 2);
		ans[1] = partition(x, y + n / 2, n / 2);
		ans[2] = partition(x + n / 2, y, n / 2);
		ans[3] = partition(x + n / 2, y + n / 2, n / 2);
		sort(ans, ans + 4);
		return ans[1];
	}
	else return chair[x][y];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) cin >> chair[i][j];
	}

	cout << partition(0, 0, N);
}