[백준 3020] 개똥벌레 (C++)

문제

백준 3020

3020번: 개똥벌레

풀이

처음에는 석순과 종유석을 입력받을 때 일일이 배열을 돌며 장애물을 계산해줬는데 당연하게도 시간 초과가 났습니다. (시간 복잡도가 N*H입니다)

따라서 누적합을 통해 시간 초과를 극복하고자 하였습니다.

먼저 석순과 종유석의 높이를 입력값으로 받습니다. (N은 항상 짝수이므로 석순과 종유석이 무조건 번갈아 나옵니다.)

높이를 각각의 배열에 체크해 둡니다.

그 후 루프를 돌며 높이마다의 석순과 종유석 개수를 누적합으로 구합니다.

예를 들어 석순의 높이가 각각 1, 3, 5라면 인덱스가 1부터 시작한다고 할 때 현재 배열에는 10101이 저장되어있습니다.

i번째 인덱스와 i-1인덱스를 더해주면서 누적합을 갱신합니다. (11223)

석순과 종유석의 개수를 합하고, 최솟값과 비교하여 데이터를 갱신해줍니다.

소스 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include<iostream> using namespace std;   int N, H; int top[500001]; int bottom[500001]; int sum[500001]; int cnt; int minobs = 987654321; int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cin >> N >> H;     for (int i = 0; i < N / 2; i++)     {         int low, high;         cin >> low >> high;         bottom[low]++;         top[H + 1 - high]++;     }     //석순 계산     for (int i = H - 1; i > 0; i--)     {         bottom[i] += bottom[i + 1];     }     for (int i = 1; i <= H; i++)     {         //종유석 계산         top[i] += top[i - 1];         //석순과 종유석 합한 후 최소값 비교         sum[i] += top[i] + bottom[i];         if (sum[i] < minobs)         {             cnt = 1;             minobs = sum[i];         }         else if (sum[i] == minobs)             cnt++;     }     cout << minobs << ' ' << cnt;     return 0; } Colored by Color Scripter

cs