BOJ 5530 JOIOI 탑

문제 링크입니다.

관찰

JOI나 IOI 탑을 만들려면 바닥에 I가 깔려야 합니다. 바닥으로 쓸 I는 위에서 가져오는 것보다 바닥에서부터 가져오는 것이 항상 이득입니다. 따라서 문제의 답이 K라면, 바닥에서부터 K개의 I만을 바닥으로 모두 쓰는 방법이 반드시 존재합니다. 이 점을 이용합니다.

결정 문제로의 환원

만들 수 있는 탑의 개수의 최댓값을 구하는 대신, 주어진 개수의 탑을 만들 수 있는지 판별하는 결정 문제를 생각할 수 있습니다. 이때 K개의 탑을 만들 수 있다면 K-1 개의 탑 역시 당연히 만들 수 있을 것이므로, 문제를 탑의 개수에 대한 이분 탐색으로 해결할 수 있습니다.

결정 문제 풀기

이분 탐색을 할 때, 관찰에서 알아 보았듯이 I의 역할을 미리 부여해 줄 수 있습니다. 마지막 K개의 I를 모두 탑의 바닥으로 사용하고, 그 전의 I는 모두 J라고 생각하고 탐색을 진행합니다.

맨 위의 판부터 시작해서,

• J가 나오면 J-탑의 개수를 1 올립니다.
• O가 나왔고 J-탑이 있다면, J-탑의 개수를 1 내리고 JO-탑의 개수를 1 올립니다.
• I가 나왔고 JO-탑이 있다면, JO-탑의 개수를 1 내리고 JOI-탑의 개수를 1 올립니다.

마지막 판까지 확인한 뒤 JOI-탑의 개수가 K와 같다면 답이 K 이상, 아니면 답이 K 미만인 것입니다. 이에 맞춰 이분 탐색을 진행하면 $\mathcal{O}(N \log N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
vector<int> I;
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n; cin >> n;
	string s; cin >> s;
	for(int i = 0; i < n; i++) if(s[i] == 'I') I.push_back(i);
	int ans = 0;
	int lo = 1, hi = I.size();
	while(lo <= hi){
		int mid = lo+hi >> 1;
		int j = 0, o = 0, i = 0;
		for(int x = 0; x < n; x++){
			if(s[x] == 'J')  j++;
			if(s[x] == 'O' && j) j--, o++;
			if(s[x] == 'I'){
				if(x < I[I.size()-mid]) j++;
				else if(o) o--, i++;
			}
		}
		ans = max(ans, i);
		if(i == mid) lo = mid+1;
		else hi = mid-1;
	}
	cout << ans;
}