백준 3020(개똥벌레) c++

문제

3020번: 개똥벌레

가로의 길이 n(짝수)과 높이 h가 주어지고, n개의 석순과 종유석이 차례대로 주어집니다.

홀수번째는 석순이 주어지고 짝수번째는 종유석이 주어집니다.

이 때 개똥벌레는 1 ~ h의 높이로 날 수 있는데 직진으로 앞에 있는 장애물을 모두 파괴할 수 있습니다.

개똥벌레가 뚫는 장애물의 개수가 최소가 되는 높이와 이 때, 최소의 개수가 총 몇개 있는지 구하는 문제입니다.

예를 들어 n = 6이고 h = 7이고, 장애물이 차례대로 (1, 5, 3, 3, 5, 1)로 주어진다면

위와 같이 장애물이 그려질 수 있고, 빨간선의 높이로 개똥벌레가 날면 최소의 장애물을 파괴할 수 있습니다.

처음에는 입력받는 부분에서 장애물 배열 arr를 만들어서 예를 들어 석순이 4로 들어오면 

arr[1], arr[2], arr[3], arr[4]에 1씩 더해주었다. 하지만 이렇게 되면 결국 반복문을 두번 돌게 되는 꼴이고, 시간초과가

발생합니다.

다른 방법을 찾아봤는데, "누적합" 으로 해결이 가능합니다.

반복문을 한번만 돌아야 하고, 한번만 돌면서 위와 같은 계산을 해줘야 하기 때문입니다.

 

먼저 배열을 top, bottom으로 만들었는데, 석순은 bottom에 저장되고, 종유석은 top에 저장됩니다.

먼저 입력 받는 부분은 막넣어줍니다.

int n, h;
   cin>>n>>h;
    
    for(int i = 1;i<=n;i++){
        int a;
        cin>>a;
        if(i%2 == 0)
            top[h-a+1]++;
        else
            bottom[a]++;
    }

i가 홀수일때는 bottom배열에, 짝수일 때는 top배열에 넣어줍니다.

주의할 점이 top배열에 넣을 때는 종유석이 위에서 아래로 되기 때문에 밑에서 볼때는 h-i+1 의 높이의 장애물이라고

볼 수 있습니다. 예를 들어 종유석의 길이가 5이면, 7 - 5 + 1 = 3, 즉, 3 ~ 7의 장애물입니다.

위의 코드를 실행하면 (index는 0이 아니라 1기준)

bottom = {1, 0, 1, 0, 1, 0, 0}

top = {0, 0, 1, 0, 1, 0, 1} 입니다.

 

이제 누적합을 적용합니다.

for(int i=h-1;i>=1;i--)
    bottom[i]+=bottom[i+1];

개똥벌레가 날 수 있는 최대 높이부터 누적합을 더해갑니다.

위에 과정을 겹치게 되면

bottom = {3, 2, 2, 1, 1, 0, 0} 이 됩니다.

즉, 1의 높이로 날면 3번 부딪히고, 2번 높이로 날면 2번, ....

이는 top일 때도 마찬가지 입니다. 즉, logic은 똑같습니다.

for(int i=h-1;i>=1;i--)
        bottom[i]+=bottom[i+1];
    int min_wall = 600000;
    int cnt=0;
    for(int i=1;i<=h;i++){
        top[i]+=top[i-1];
        result[i]+=(top[i]+bottom[i]);
        if(result[i]<min_wall){
            min_wall=result[i];
            cnt=1;
        }
        else if(result[i]==min_wall)
            cnt++;
    }
    cout<<min_wall<<' '<<cnt;

위에 과정을 겹치면 

top = {0, 0, 1, 1, 2, 2, 3} 이 되고, 

bottom과 top을 합치면 

result = {3, 2, 3, 2, 3, 2, 3} 이 됩니다. 결국 최솟값은 2가 되고 빈도수는 3이 됩니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>

#define INF 2000000000
using namespace std;
using ll = long long;
int top[500001];
int bottom[500001];
int result[500001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n, h;
    cin>>n>>h;
    
    for(int i = 1;i<=n;i++){
        int a;
        cin>>a;
        if(i%2 == 0)
            top[h-a+1]++;
        else
            bottom[a]++;
    }

    for(int i=h-1;i>=1;i--)
        bottom[i]+=bottom[i+1];
    int min_wall = 600000;
    int cnt=0;
    for(int i=1;i<=h;i++){
        top[i]+=top[i-1];
        result[i]+=(top[i]+bottom[i]);
        if(result[i]<min_wall){
            min_wall=result[i];
            cnt=1;
        }
        else if(result[i]==min_wall)
            cnt++;
    }
    cout<<min_wall<<' '<<cnt;
    

	return 0;
}