[BOJ 5837] Poker Hands

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

5837번: Poker Hands

Tag : Greedy

 

문제요약

구간 [l,r]의 모든 원소를 1씩 줄일 수 있는 연산이 있고 모든 원소를 0으로 만드는 것이 목표일 때

최소 연산 횟수를 구하는 문제다.

 

풀이

가능한 선에서 구간을 크게 잡는 것이 항상 이득이다. 그렇기 때문에 [l,r]에서 최소가 0이 될때까지 쭉 빼주고

그 최소가 0이 된다면, 그것을 기준으로 구간을 줄여나가면 된다.

일단은 빨리 ac를 맞으려고 세그먼트 트리를 사용했다.

 

sol1) 세그먼트 트리, \(O(NlogN)\)

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N;
ll ans=0;
ll v[101010];
pl tree[303030];

pl query(ll l,ll r){
    pl ret={1e18,0};
    for(l+=N,r+=N;l<=r;l>>=1,r>>=1){
        if(l&1)rmin(ret,tree[l++]);
        if(~r&1)rmin(ret,tree[r--]);
    }
    return ret;
}

void f(ll l,ll r,ll h){
    if(l>r)return;
    auto[mn,idx]=query(l-1,r-1);mn-=h;
//    cout<<l<<' '<<r<<" : "<<mn+h<<' '<<idx<<endl;
    if(mn>0)ans+=mn;
    f(l,idx-1,h+mn);f(idx+1,r,h+mn);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N;
    for(int i=0;i<=3*N;i++)tree[i]=pl(1e18,0);
    for(int i=0;i<N;i++){
        cin>>tree[N+i].fi;
        tree[N+i].se=i+1;
    }
    for(int i=N-1;i>=1;i--)tree[i]=min(tree[i<<1],tree[i<<1|1]);
    f(1,N,0);
    cout<<ans<<endl;
}

---

sol2) 관찰, \(O(N)\)

\(A_i = | v_i-v_{i-1} |\)로 정의된 수열을 \([1,N)\)에 대해 만들어보자.

우리는 항상 가능한 가장 큰 범위를 잡아 줄여나가기 때문에 \(A_i\)의 합은 2씩 줄어든다.

따라서 \(\lfloor{\frac{\sum{A_i}}{2}}\rfloor\)가 정답이다.

 

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}



int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    ll N,ans=0;
    cin>>N;
    ll x,pre=0;
    for(int i=1;i<=N;i++){
        cin>>x;
        ans+=abs(x-pre);
        pre=x;
    }
    ans+=abs(x);
    cout<<ans/2<<endl;
}