BOJ 17955 - Max or Min

문제 태그 : https://www.acmicpc.net/problem/17955

나한테 잘 맞는 문제였다. 정말 좋은 문제라고 생각한다.

문제 소개

n,m이 주어진다. 이후 1 이상 m 이하의 수 n개가 주어진다. n개의 숫자는 원형으로 이루어져 있다. 이후 2가지 행동을 할 수 있다.
1. 어떤 한 칸을 골라 그 수를 max(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다.
2. 어떤 한 칸을 골라 그 수를 min(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다.

원형으로 이루어진 n개의 숫자를 모두 (1,2,3,...m)으로 만드는데 필요한 최소 행동의 횟수를 각각 구하시오. 만약 만들 수 없다면 -1을 출력한다.

문제 풀이 

스포 주의!

Step1. 문제 관찰

문제의 예제를 봄으로써 몇가지 사실을 관찰 할 수 있다.

1. 배열에 존재하지 않는 수는 절대로 만들 수 없다. (-1이 나온다.)
2. 배열에 존재하는 수는 무조건 만들 수 있다. 
3. 어떤 연속된 세개의 숫자에 대해서 k가 중간 값이 아니라면 가운데 숫자를 1번의 행동으로 k로 만들 수 있다.
4. 최댓값 최솟값에 집중을 해보자. 최댓값은 나머지 모두를 1번 행동을 함으로써 완성시킬 수 있고, 최솟값은 나머지 모두를 2번 행동을 함으로써 완성시킬 수 있다.
5-1. 그 밖의 숫자에 주목을 해보자. 4에 해당하지 않는 숫자 k가 있을 때, 나머지 모두를 1번행동을 한 뒤, 2번 행동을 하면 모두 k로 만들 수 있다.
5-2. k보다 큰 숫자에 대해서는 1번 행동을 하지 않아도 된다.
5-3. 이와 반대의 경우에도 성립한다. (2번 행동 후 1번행동)
6. 따라서 어떤 k에 대해서 현재 구할 수 있는 답은 최대 min(k보다 큰 숫자의 갯수, k보다 작은 숫자의 갯수)+k가 아닌 숫자의 갯수 이다. 

나는 위와 같은 관찰을 하였다. 이 관찰을 모두 하는 것은 분명히 쉽지 않다. 하지만, 이 부분이 나의 강점이다. 직접 상황을 만들어보고 계속 시행을 해보고 예제를 연구하면서 관찰을 할 수 있었다. 

여기까지의 관찰을 토대로 좀 더 세밀화 된 상황을 만들고 추가적인 관찰을 해야한다. 여기까지 글을 읽었다면 아래의 내용을 읽기 전에 좀 더 생각하는 시간을 가져보는 것을 추천한다. 바로 남의 풀이과정을 따라가기에는 좀 아까운 문제이다. 

Step 2. 추가 관찰+ 풀이 기초

일단 관찰 4,5를 통해서 k보다 큰 숫자와 작은 숫자만 의미가 있다는 것을 알았다. 따라서 1,2,3만 있는 상황을 생각해보자. 4에 의해서 1,3에 대해서는 구하기 쉽다. 하지만, F(2)를 구하는 것이 이 상황의 목적이다. 두가지 상황에 대한 값을 생각해보면 6번에서 갯수가 아닌 다른 것에 영향을 받는다는 사실을 알 수 있다.

Case 1:  2 1 1 3 3  
a2에 max 취하기 a5에 min 취하기 a3에 max 취하고 min취하기 a4에 min 취하기 -> 5회

Case 2:  2 1 3 1 3  
a2에 max 취하고 min 취하기 a4에 max 취하기 a5에 min 취하기 a3에 min 취하기 a4에 min취하기 -> 6회

Case 3:  2 1 3 3 1  
a2에 max 취하고 min 취하기  a3에 min 취하기 a4에 max 취하기 a5에 min 취하기 a4에 min취하기 -> 6회

이러한 상황들을 다시 관찰하고 3번 관찰을 보자. 뭔가 떠오르는 것이 생긴다. 연속된 1은 한쪽 끝이 2이면 계속 max를 취해주면서 쭉 2로 만들 수 있다. 3의 경우도 마찬가지. 여기서 중요한 것은 1,3 이 연속되어있을 때라는 것을 알 수 잇다. 이때 두 개를 둘 다 2로 만들기 위해서는 3번의 작업이 필요하다.

여기서 주의할 점은 1번의 (1,3) 당 한번의 추가 작업이 아니라 (1,3)을 합쳐서 3번이라는 것이다. 이 때문에 Case 2는 7번이 아닌 6번이 되는 것이다. 

따라서 최종적으로 결론을 내자면 F(k)를 구하기 위해서는 k의 갯수와 (k보다 큰 숫자, k보다 작은 숫자)의 묶음을 구하면 된다. 

Step 3. 풀이 세분화  + 구현방식 생각

어떤 k에 대해서 그룹을 몇개 만들어 줄 수 있는지에 대해서 세는 것이 아니라 배열의 인접한 두 원소를 잡고 그 사이의 값을 업데이트 하는 느낌으로 해결할 수 있다. (a1,a2)를 업데이트 하고 (a2,a3)-(a1,a2) (집합에서 빼는 형식) 을 업데이트하고 ...  마지막에 (an-1,an)-(an-2,an-1)-(a1,an)을 업데이트하면 연속해서 두번을 업데이트 하는 경우가 존재하지 않는다. 

말로하면 이해가 어렵기 때문에 예제를 예시로 들려고 한다.

(2,5) -> [3,4]  0 0 1 1 0
(1,5)-(2,5) ->[2,4]-[3,4] ->[2,2]  0 1 1 1 0
(1,1) -> X  0 1 1 1 0
(1,2) -> X 0 1 1 1 0
(2,3) -> X 0 1 1 1 0
(2,3) -> X 0 1 1 1 0
(2,2) -> X 0 1 1 1 0

F(1)=7-2+0=5 F(2)=7-3+1=5 F(1)=7-1+1=7 F(4)=-1 F(5)=7-1+0=6

위와 같은 방식으로 답이 도출되는 것을 확인할 수 있다. 구현은 Range Upate Point Query이므로 Segment Tree with Lazy propagation을 짜주면 될 것이다. 

여기서 한 가지 문제가 생기게 되는데, 이는 첫 구간을 항상 사용한다고 했기 때문에 어떤 숫자에 대한 최대 그룹의 갯수가 나오지 않을 수 있다. 따라서 한칸씩 돌린 후 위의 과정을 한 번더 진행해준후 max값을 뽑아내면 된다.

코드

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll arr[1010101];
ll arr2[1010101];
ll cnt[1010101];
ll ans[1010101];
ll ans2[1010101];
 
 
struct node{
    ll val,laz;
};
node tree[5101010];
 
void upt(ll l,ll r,ll s,ll e,ll nod){
    //printf("%lld %lld %lld %lld %lld\n",l,r,s,e,nod);
    if(tree[nod].laz!=0){
        tree[nod].val+=tree[nod].laz;
        tree[nod*2].laz+=tree[nod].laz;
        tree[nod*2+1].laz+=tree[nod].laz;
        tree[nod].laz=0;
    }
    if(r<s||e<l) return ;
    if(l<=s&&e<=r){
        tree[nod].laz++;
        return ;
    }
    upt(l,r,s,(s+e)/2,nod*2);
    upt(l,r,(s+e)/2+1,e,nod*2+1);
}
 
ll sol(ll idx,ll s,ll e,ll nod){
    if(tree[nod].laz!=0){
        tree[nod].val+=tree[nod].laz;
        tree[nod*2].laz+=tree[nod].laz;
        tree[nod*2+1].laz+=tree[nod].laz;
        tree[nod].laz=0;
    }
    if(idx<s||idx>e) return 0;
    if(s==e) return tree[nod].val;
    return sol(idx,s,(s+e)/2,nod*2)+sol(idx,(s+e)/2+1,e,nod*2+1);
}
 
node tree2[3101010];
 
void upt2(ll l,ll r,ll s,ll e,ll nod){
    if(tree2[nod].laz!=0){
        tree2[nod].val+=tree2[nod].laz;
        tree2[nod*2].laz+=tree2[nod].laz;
        tree2[nod*2+1].laz+=tree2[nod].laz;
        tree2[nod].laz=0;
    }
    if(r<s||e<l) return ;
    if(l<=s&&e<=r){
        tree2[nod].laz++;
        return ;
    }
    upt2(l,r,s,(s+e)/2,nod*2);
    upt2(l,r,(s+e)/2+1,e,nod*2+1);
}
 
ll sol2(ll idx,ll s,ll e,ll nod){
    if(tree2[nod].laz!=0){
        tree2[nod].val+=tree2[nod].laz;
        tree2[nod*2].laz+=tree2[nod].laz;
        tree2[nod*2+1].laz+=tree2[nod].laz;
        tree2[nod].laz=0;
    }
    if(idx<s||idx>e) return 0;
    if(s==e) return tree2[nod].val;
    return sol2(idx,s,(s+e)/2,nod*2)+sol2(idx,(s+e)/2+1,e,nod*2+1);
}
 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,l,m,n;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>arr[i];
        cnt[arr[i]]++;
    }
    arr[n+1]=arr[1];
    arr[n+2]=arr[2];
    for(i=1;i<=n+1;i++)
        arr2[i]=arr[i+1];
 
    ll fs,fe,ls,le,ns,ne;
    fs=ls=min(arr[1],arr[2])+1;
    fe=le=max(arr[1],arr[2])-1;
 
    upt(ls,le,1,m,1);
    for(i=3;i<=n;i++){
        ns=min(arr[i],arr[i-1])+1;
        ne=max(arr[i],arr[i-1])-1;
        if(ne<ns){
            ;
        }
        else if(ls<=ns&&ne<=le){
            ns=1e18;
            ne=0;
        }
        else if(le<ns||ne<ls){
            ;
        }
        else if(le==ne&&ns<ls){
            ne=ls-1;
        }
        else if(ls==ns&&le<ne){
            ns=le+1;
        }
        //printf("%lld %lld %lld\n",i,ns,ne);
        upt(ns,ne,1,m,1);
        ls=ns;
        le=ne;
    }
    i=n+1;
    ns=min(arr[i],arr[i-1])+1;
    ne=max(arr[i],arr[i-1])-1;
    if(ne<ns){
        ;
    }
    else if(ls<=ns&&ne<=le){
        ns=1e18;
        ne=0;
    }
    else if(le<ns||ne<ls){
        ;
    }
    else if(le==ne&&ns<ls){
        ne=ls-1;
    }
    else if(ls==ns&&le<ne){
        ns=le+1;
    }
 
    if(ne<ns){
        ;
    }
    else if(fs<=ns&&ne<=fe){
        ns=1e18;
        ne=0;
    }
    else if(fe<ns||ne<fs){
        ;
    }
    else if(fe==ne&&ns<fs){
        ne=fs-1;
    }
    else if(fs==ns&&fe<ne){
        ns=fe+1;
    }
    upt(ns,ne,1,m,1);
 
 
 
    fs=ls=min(arr2[1],arr2[2])+1;
    fe=le=max(arr2[1],arr2[2])-1;
 
    upt2(ls,le,1,m,1);
    for(i=3;i<=n;i++){
        ns=min(arr2[i],arr2[i-1])+1;
        ne=max(arr2[i],arr2[i-1])-1;
        if(ne<ns){
            ;
        }
        else if(ls<=ns&&ne<=le){
            ns=1e18;
            ne=0;
        }
        else if(le<ns||ne<ls){
            ;
        }
        else if(le==ne&&ns<ls){
            ne=ls-1;
        }
        else if(ls==ns&&le<ne){
            ns=le+1;
        }
        upt2(ns,ne,1,m,1);
        ls=ns;
        le=ne;
    }
    i=n+1;
    ns=min(arr2[i],arr2[i-1])+1;
    ne=max(arr2[i],arr2[i-1])-1;
    if(ne<ns){
        ;
    }
    else if(ls<=ns&&ne<=le){
        ns=1e18;
        ne=0;
    }
    else if(le<ns||ne<ls){
        ;
    }
    else if(le==ne&&ns<ls){
        ne=ls-1;
    }
    else if(ls==ns&&le<ne){
        ns=le+1;
    }
 
    if(ne<ns){
        ;
    }
    else if(fs<=ns&&ne<=fe){
        ns=1e18;
        ne=0;
    }
    else if(fe<ns||ne<fs){
        ;
    }
    else if(fe==ne&&ns<fs){
        ne=fs-1;
    }
    else if(fs==ns&&fe<ne){
        ns=fe+1;
    }
    upt2(ns,ne,1,m,1);
 
    for(i=1;i<=m;i++){
        if(cnt[i]==0) printf("-1 ");
        else printf("%lld ",n-cnt[i]+max(sol(i,1,m,1),sol2(i,1,m,1) ));
 
        //printf("%lld %lld %lld %lld\n",i,cnt[i],sol(i,1,m,1),sol2(i,1,m,1));
    }
 
}