[백준] 개똥벌레(3020)

문제 링크 : [백준] 개똥벌레(3020)

문제 설명

높이가 h인 동굴에 바닥에서 솟은 n/2개의 석순과 천장에서 내려오는 n/2개의 종유석이 있을 때, 개똥벌레가 어떤 높이로 날아야 최소한으로 장애물에 부딪히며 동굴을 통과하는지 갯수와 그러한 구간이 몇개가 있는지 구하는 문제입니다.

입력

n(종유석 + 석순의 갯수,2<=n<=200,000(n은 짝수))
h(동굴의 높이, 2<=h<=500,000)
D_i(i는 홀수, 석순의 높이)
D_j(j는 짝수, 종유석의 길이)

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

출력

최소로 부딪히는 갯수, 그런 구간의 갯수

7 2

카테고리

#정렬 #누적합

시간 복잡도 상한

O(n*h)는 제한 시간을 넘어서게 됩니다..
O(nlogn), O(hlogh)정도까지 가능합니다.

해결 방법

1. 땅에서 천장 방향으로 높이를 1씩 증가하면서 부딪히는 갯수를 세게 되면
   1-1. 석순의 경우, 석순의 높이보다 1높아지는 지점에서 해당 석순에 부딪히지 않게되므로, 부딪히는 갯수가 1 줄어들게 됩니다.
   1-2. 종유석의 경우, h-종유석의 길이보다 1높아지는 지점에서 해당 종유석에 부딪히게 되므로, 부딪히는 갯수가 1 늘어나게 됩니다.
2. 1 속성을 이용하여 각 높이로 변경 될 때, 몇개의 장애물이 새로 부딪히는지, 덜 부딪히게 되는지를 배열에 저장합니다.
3. 2에서 구한 배열을 가지고, 0 ~ h까지 누적 합들을 구하면서, 최소로 부딪히는 값과 그 구간의 갯수를 구한다.

시간복잡도

O(n+h)

코드

#include<cstdio>
int d[500001],N,H,s=1,t,a=1;
int main(){
    scanf("%d %d", &N, &H);
    for(int i=0;i<N;i++) {
        scanf("%d",&t);
        if(a)d[t + 1]--;
        else d[H-t+1]++;
        a^=1;
    }
    for(int i=1;i<=H;i++)d[i]+=d[i-1];
    t=d[1];
    for(int i=2;i<=H;i++){
        if(t>d[i])s=1,t=d[i];
        else if(t==d[i])s++;
    }
    printf("%d %d",t+(N/2),s);
}