POI Deque 문제(BOJ 8201번 Pilots , 10129번 작은 새)

먼저 Deque dp나 Deque를 이용한 테크닉에 잘 모르거나 익숙하지 않다면 다음 글을 보고 오자.

https://chpark1111.tistory.com/8

자료구조 덱(deque)의 활용

 

8201번 Pilots https://www.acmicpc.net/problem/8201

 

풀이 : 최솟값, 최댓값 덱을 만들고 덱에서 최댓값, 최솟값들의 인덱스 차이가 t 이상 나지 않도록 관리해주면서 가능한 구간의 최댓값을 갱신해주면 된다. 이때, 덱 2개를 관리하므로 구간 길이를 구할 때 사용할 하한을 따로 잡아줘야 한다. (당연하지만 상한은 for문 i값) 또한, 이 문제는 자료구조 덱 활용 글에서 말했듯이 우선순위 큐로도 풀 수 있으며 세그먼트 트리를 만들어서도 풀 수 있다. (세그트리는 구현이 익숙하지 않을 때 작성해서... 변수들 이름이 길고 코드가 조금 지저분하다.)

 

소스 코드(Pilots)

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ll t,n,anw=1,del;
vector<ll> arr;
deque<ll> u,d;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t>>n;
    for(int i=0;i<n;i++)
    {
        ll a;cin>>a;
        arr.push_back(a);
    }
    for(ll i=0;i<n;i++)
    {
        while(!u.empty()&&arr[u.back()]>=arr[i]) u.pop_back();
        while(!d.empty()&&arr[d.back()]<=arr[i]) d.pop_back();
        u.push_back(i);d.push_back(i);
        while(arr[d.front()]-arr[u.front()]>t)
        {
            if(d.front()==del) d.pop_front();
            if(u.front()==del) u.pop_front();
            del++;
        }
        anw=max(anw,i+1-del);
    }
    cout<<anw;
    return 0;
}

소스 코드(Pilots, segment tree 버전)

#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
 
const ll INF=numeric_limits<ll>::max();
const ll DINF=numeric_limits<ll>::min();
ll t,n,anw=1,lc,hc,st,en;
vector<ll> arr,rangemin,rangemax;
 
ll minit(const vector<ll>& a,int left,int right,int node)
{    
    if(left==right)    return    rangemin[node]=a[left];
    int mid=(left+right)/2;        
    return rangemin[node]=min(minit(a,left,mid,node*2),
                                            minit(a,mid+1,right,node*2+1));
}
 
ll mainit(const vector<ll>& a,int left,int right,int node)
{    
    if(left==right)    return    rangemax[node]=a[left];
    int mid=(left+right)/2;        
    return rangemax[node]=max(mainit(a,left,mid,node*2),
                                            mainit(a,mid+1,right,node*2+1));
}
 
ll askm(int left,int right,int node,int nodeleft,int noderight)
{
    if(right<nodeleft||noderight<left)    return INF;
    if(left<=nodeleft&&noderight<=right)    return rangemin[node];
    int mid=(nodeleft+noderight)/2;
    return min(askm(left,right,node*2,nodeleft,mid),
                    askm(left,right,node*2+1,mid+1,noderight));    
}
 
ll asku(int left,int right,int node,int nodeleft,int noderight)
{
    if(right<nodeleft||noderight<left)    return DINF+1;
    if(left<=nodeleft&&noderight<=right)    return rangemax[node];
    int mid=(nodeleft+noderight)/2;
    return max(asku(left,right,node*2,nodeleft,mid),
                    asku(left,right,node*2+1,mid+1,noderight));    
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t>>n;
    rangemin.resize(4*n);
    rangemax.resize(4*n);
    for(int i=0;i<n;i++)
    {
        ll a;cin>>a;
        arr.push_back(a);
    }
    mainit(arr,0,n-1,1);
    minit(arr,0,n-1,1);
    while(1)
    {
        if(lc==0&&hc==0)
        {
            lc=arr[0];hc=arr[0];
        }
        while(abs(lc-hc)<=t&&st<n)
        {
            st++;
            hc=max(hc,arr[st]);lc=min(lc,arr[st]);
        }
        anw=max(anw,st-en);
        while(abs(lc-hc)>t&&en<n)
        {
            if(hc==arr[en])
                hc=asku(en+1,st,1,0,n-1);
            if(lc==arr[en])
                lc=askm(en+1,st,1,0,n-1);
            en++;
        }    
        if(st==n)
        {
            if(abs(lc-hc)<=t)
                anw=max(anw,st-en-1);
            break;
        }
    }
    cout<<anw;
    return 0;
}

 

10129번 작은 새 https://www.acmicpc.net/problem/10129

 

풀이 : 현재 높이보다 다음 나무의 높이가 높은지 낮은지 여부로 1을 더할지 말지를 정하고, 다른 거는 일반적인 deque 테크닉처럼 해주면 된다. 하지만 이 문제의 핵심은 우선순위를 어떻게 비교하는지다. deque의 back에서 우선순위를 비교할 때 당연히 값이 더 크면 큰 쪽이 우선순위가 낮아지지만, 값이 같을 경우에는 현재 그 값을 가지면서 올라가 있는 나무의 높이를 비교해 우선순위를 결정해야한다. 올라가 있는 나무의 높이가 높을수록 다음 나무를 1을 더하지 않고 넘을 수도 있기 때문에 값이 같다면 나무의 높이가 높은 쪽이 우선순위가 높다고 해야한다. 

 

소스 코드(작은 새)

#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll,ll> pi;
 
ll n,q,dp[1000004];
deque<pi> dq;
vector<ll> h,b;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        ll a;cin>>a;
        h.push_back(a);
    }
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int a;cin>>a;dq.clear();
        dq.push_back({0,0});
        for(int i=1;i<n;i++)
        {
            while(!dq.empty()&&dq.front().first+a<i) dq.pop_front();
            pi now;
            if(h[dq.front().first]<=h[i])
                now={i,dq.front().second+1};
            else
                now={i,dq.front().second};
            while(!dq.empty()&&dq.back().second>=now.second)
            {
                if(dq.back().second>now.second)
                    dq.pop_back();
                else
                {
                    if(h[dq.back().first]<=h[i])
                        dq.pop_back();
                    else break;
                }
            }
            if(i==n-1)
                cout<<now.second<<"\n";
            dq.push_back(now);
        }
    }
    return 0;
}