August 18, 2019 22:25

문제 요약

문제 링크

$N$층의 피라미드가 있다. $i$번째 층에는 $2i - 1$개의 칸이 있다.

피라미드의 $N$층에 $1, 2, \cdots, 2N-1$을 적절히 섞은 순열이 쓰여 있다. $1$층 부터 $N-1$층 까지의 칸에 숫자를 채우는 규칙은, 그 칸에 있는 수가 그 칸 아래쪽에 있는 $3$개의 수의 중앙값이라는 것이다.

위 방법에 따라 피라미드를 채웠을 때, $1$층에 있는 칸에 쓰인 숫자를 구해라.

$ 2 \le N \le 10^5 $

풀이

1. $O(N^2)$

규칙에 맞춰서 모든 칸의 값을 구해본다. 공간복잡도가 $O(N^2)$라고 생각할 수 있지만, $i$번째 층을 채우는 데에는 $i+1$번째 층의 정보만 필요함으로, 토글링 등을 이용하여 공간복잡도를 $O(N)$으로 줄여서 해결할 수 있다.

다만 시간초과가 난다.

2. $O(N \log N)$

아이디어를 소개한다. 이분탐색을 이용하여 답을 구할 수 있다.

어떤 $1 \le x \le 2N-1$에 대해서 “답이 $x$이상인가?”라는 질문에 답해보자. 이제 $N$ 층에 쓰여진 숫자에 대해서, $x$ 미만이면 $0$, $x$ 이상이면 $1$로 바꾸면, “$1$ 층에 있는 값이 $1$인가?” 라는 문제로 바뀐다. 이제 이 문제를 풀어보자.

성질을 몇 가지 찾아보자.

인접한 칸이 같은 숫자인 경우 ($0 0$ or $1 1$) 그 위에 칸은 모두 같은 숫자로 도배된다. $a 0 0 b$ 을 예시로 들면, 그 윗층에 대해서 $c 0 0 d$ 로 확정되기 때문이다. ($3$개의 값 중, $2$개가 $0$이므로 중앙값은 $0$ 이다.)

그러면 남은 경우는 어떤 칸에 대해서, 양 옆의 칸이 같은 숫자가 아닌 경우 ($0 1 0$ or $1 0 1$)이다. 이 경우는 자연스럽게 윗 층에 채워지는 값이 $a 0 b$ or $c 1 d$가 된다.

위 두 성질을 발견했으므로, 일반적인 경우에 대해서 상상해보자. 아래 그림을 살펴보자.

인접한 칸이 같은 숫자인 묶음이 한 층을 올라갈 때 마다, 영역이 양 옆으로 한 칸씩 늘어남을 관찰할 수 있다. 만약 두 묶음이 만나게 되면, 영역이 그대로 유지됨을 알 수 있다. 즉, 이 영역싸움에서 $1$층에 쓰여질 값이 무엇인지 찾으면 된다.

같은 값을 가지는 인접한 묶음이 점점 영역을 양옆으로 한 칸씩 늘어나므로, $1$층 칸의 열 ($N$번째 열)에 가장 가까운 묶음이 $1$층 칸을 점령할 것 이다. 즉, $N$ 열에 인접한 칸의 값이 같은 가장 가까운 값이 정답이 된다. 만약, 인접한 칸의 값이 같은 경우가 없다면 $0 1 0 1 0 \cdots 0 1 0$ 등의 자명한 경우이므로, 따로 처리해주면 된다.

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
 
const int MAX_N = 2e5 + 100;
 
int Nr[MAX_N], N;
bool isCan(int k) {
	int minAbs = MAX_N * 10, val = -1;
	for(int i=1; i<2*N-1; i++) {
		int nowAbs = min(abs(N-1-i), abs(N-1-i+1));
		if((Nr[i] >= k) == (Nr[i-1] >= k) && minAbs > nowAbs) minAbs = nowAbs, val = (Nr[i] >= k);
	}
	if(val == -1) val = (Nr[0] >= k);
//	printf("%d -> %d\n", k, val);
	return val;
}
int main() {
	cin >> N;
	for(int i=0; i<2*N-1; i++) scanf("%d", &Nr[i]);
	int ans = -1;
	for(int l=1, r=2*N-1; l<=r; ) {
		int m = (l+r) >> 1;
		if(isCan(m)) ans = m, l = m+1;
		else r = m-1;
	}
	printf("%d\n", ans);
 
	return 0;
}