[BOJ/8201] Pilots, c++

www.acmicpc.net/problem/8201

8201번: Pilots

한줄 후기 : 영어 해석은 papago..

 

신촌 알고리즘 중급 캠프 덱 DP 강좌 필수 문제였다.

사실 필수 문제를 다 읽어봤는데 (다이아는 보지도 않음) 내가 풀 수 있어 보이는게 없었음ㅋㅋㅋ..

골드 1 문제는 비트 마스킹인데 난 진짜 못하겠더라 .. (나중에 풀어보자..!)

그래서 덱 dp를 울며 겨자먹기로 .. 

 

대충 해석하자면 

어떤 t값이 주어지고 수열이 들어오는데, 구간 내에 최댓값 - 최솟값 <= t 인 최대 구간 길이를 구하면 된다. 

처음에 해석 잘못 해서 최댓값 위치 - 최솟값 위치로 찾고 있었음 ;;

사실 절대 내 머리로 완전 다 푼건 아니고,, 

deque 2개를 써야하는데 감이 안와서 구글에 조금 찾아 봤다. max, min deque 두개를 쓰면 된다.

max 덱에는 구간 내에 최댓값을 관리해 주는데 front 부분에 가장 최댓값이 들어있게 된다.

항상 숫자를 받았을 때 back 이 나보다 작으면 다 pop 시켜 버리면 덱 안에 내림차순으로 들어가게 된다. 

최솟 값은 반대로 생각하면 됨! front에 항상 구간 내에 최솟값을 넣어두면 된다.

 

즉, 1, 3, 2, 5 면

처음에 1이 들어가고 다음 3이 들어갈 때 덱의 back 부분인 1은 3보다 작으니 더이상 뒤에서 최댓값이 될 수 없게 된다. 그러면 그냥 pop 하고 3을 넣는다.

2가 들어오면 또 보는데 이번에 덱에 있는 3은 2보다 크니 후에 최댓값이 될 수 있는 후보로 놔둔다.

그리고 2를 집어넣자.

마지막 5가 들어오면 덱에는 2개가 있게 되는데 3, 2 이다. back부터 보면서 2는 5보다 작으니 앞으로 최댓값이 될 가능성이 없다. pop하자. 3 역시 5보다 작으므로 더 이상 최댓값이 될 가능성이 없어 pop 한다.

그러면 5를 push하고 결과적으로 deque의 front에 있는 5가 1,3,2,5 구간 내의 최댓값이 되는 것이다.

 

//
//BOJ 8201 Pilots
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
typedef long long ll;
deque<pair<ll, ll> > maxd;
deque<pair<ll, ll> > mind;
ll max_l(ll a, ll b){
	return a >= b ? a : b;
}
vector<int> arr;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, num, ck = 0;
	ll t, gap = 0, ans = 0;
	cin >> t >> n;
	for(int i=0; i<n; i++){
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
		if(i!=0 && arr[i] != arr[i-1])	ck = 1;
	}
	for(int i=1; i<=n; i++){
		num = arr[i-1];
		while(!maxd.empty() && maxd.back().first <= num){
			maxd.pop_back();
		} 
		while(!mind.empty() && mind.back().first >= num){
			mind.pop_back();
		}
		maxd.push_back({num, i});
		mind.push_back({num, i});
		while(maxd.front().first - mind.front().first > t){
			if(maxd.front().second > mind.front().second){
				gap = mind.front().second;
				mind.pop_front();	
			}
			else{
				gap =  maxd.front().second;
				maxd.pop_front(); 
			}
		}
		ans = max_l(ans, i - gap);
		
	}
	if(!ck)	cout << n;
	else	cout << ans;
//	cout << ans;
	return 0;
} 

 그렇게 최대/ 최소 deque을 관리해주면 이제 t를 검사해줘야한다.

pop과 push를 마친 후에 각 deque의 front 부분 (최대/최소) 그 값들의 차를 t와 검사해보고 t보다 커지면 이제 구간 길이를 검사해야 하므로 더 오래된(?) 앞에 있는 index를 뽑아낸다. 그러고 당연히 그 구간은 더이상 쓸 수 없으므로 뽑아낸 idx 는 pop해줘야한다.

마지막으로 구간 최댓값을 저장할 ans와 현재 위치 i - gap (가장 오래된 idx) 를 비교해서 항상 최대 길이를 넣어준다.

어렵다.

 

** 추가로 내가 쓴 ck는 모든 수열의 값이 같을 때는 항상 차가 0이므로 그냥 n을 출력하는건데 사실 없어도 된다. i-gap에서 어차피 n-gap이 될테니