백준 3020 개똥벌레

www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

 

이 문제의 제한조건을 보자. 일단 중요한 건 종유석과 석순의 길이대로 일일이 ++을 해주는 식으로 풀 수는 없다.

H가 50만, N이 20만이기 때문이다. 아래의 그림을 보자.

 

위에서처럼, 입력을 N번 받고, 그때마다 0부터 k까지 확인하며 2차원 배열 arr안에 1을 채워나가는 방식으로 풀려고 한다면 시간적으로도 공간적으로도 효율적이지 못하다. 애초에 20만 곱하기 50만짜리 2차원 배열을 만드는 것부터 잘못되었다. 

 

석순 3이라는 숫자를 보자. 석순 값으로 3이 주어졌다면, 1,2,3을 채운다는 사실을 알 수 있다. 즉, 3을 보고 루프를 돌아 1,2,3을 채우지 않고도 1,2,3을 채울 수 있는 방법을 생각해야 하는 것이다. 이제 아래의 그림을 보자.

문제에서 주어진 값들 중에 짝수번째, 즉 석순에 해당하는 값만 뽑아서 나열하였다. 그리고 각 숫자별로 몇번이 나왔는지 세는 것이다. 문제의 조건에서 입력값은 양수이므로 0은 생각하지 않아도 된다. 그렇게 석순의 높이를 나타내는 각 숫자별 등장 횟수를 기록해둔 후, H-1에서부터 1까지 내려가면서 누적해주면 된다. 위의 예시에서는 H-1은 4가 되고, 4가 있다는 것은 1,2,3도 있다는 뜻이므로 아래로 누적해가면 1은 7번 나온다는 뜻이 된다. 

아까 안 좋은 예시로 들었던 O(NH)에서 O(N)+O(H)로 개선된 것이다.

 

이제 종유석이다. 종유석도 똑같은 아이디어로 누적해주면 되는데, 중요한 것은 석순으로의 환산이 되겠다.

위의 그림과 같이 H+1-K를 통해 종유석에서 석순으로 환산(?)이 가능해진다. 종유석은 2부터 H까지를 아우름에 주의한다. 

그리고 석순 값들과 종유석 값들을 그대로 더해주면, 그림과 같이 7이 최소값이고 2번 나온다는 것을 바로 알 수 있다.

 

아래는 C++코드이다.

석순은 hits로 표현하였고, 종유석은 hits_rev이다. 

인덱스에 주의하자

#include <iostream>
#define endl '\n'
using namespace std;
const int sz=5e5+1;
int t,mn,hold,k,n,h,hits[sz],hits_rev[sz];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>n>>h;
    for(int i=0;i<n;++i){
        cin>>k;
        if(i%2)hits_rev[h+1-k]++;
        else hits[k]++;
    }
    for(int i=h-1;i>0;--i){
        hits[i]+=hold;
        hold=hits[i];
    }
    hold=0;
    for(int i=1;i<=h;++i){
        hits_rev[i]+=hold;
        hold=hits_rev[i];
    }
    mn=n/2+1;
    for(int i=1;i<=h;++i){
        hits[i]+=hits_rev[i];
        if(hits[i]<mn){
            t=1;
            mn=hits[i];
        }else if(hits[i]==mn) t++;
    }
    cout<<mn<<' '<<t;
    return 0;
}