[3020번] 개똥벌레

문제 출처 :

https://www.acmicpc.net/problem/3020

알고리즘 분석 :

문제 해결에 필요한 사항

1. Prefix Sum :: http://www.crocus.co.kr/843

이 문제를 푸는데 우선 http://wootool.tistory.com/117 이 블로그에서 많은 영감을 얻었다.

시작전에 이 문제를 보고 prefix sum으로는 하는 방법이 없을까 생각을 하다 검색을 해보니 이러한 방식으로 풀 수 있다는 것을 알게되고 풀이를 이해하고 나의 코드로 재해석 한 내용을 기술하려 한다.

이 문제가 Prefix Sum으로 해석이 되는 이유는 다음과 같다.

석순(아래에서 위로 올라오는 것)을 기준으로 생각해보자.

석순의 길이가 3 4 5가 있다면 개똥벌레가 높이 3에서 석순을 파괴하고 갈 때 3을 먼저 파괴하면 

그다음은 무조건 4, 5를 파괴하게 된다.

반대로 높이 4에서 석순을 파괴하면 4,5만 파괴하고 3은 파괴하지 않는다.

따라서 bottom[i]라는 배열을 생성하고 i번째의 누적 석순을 모두 저장해둔다.

(마찬가지로 종유석도 top[i] 를 통해 저장한다.)

이후 totalBottom[i]의 의미는 i번째 석순을 파괴하며 지나가게 될 때 파괴되는 모든 석순을 모아두는 것이다.

결국 이 과정이 Prefix Sum으로 해석 될 수 있다.

이렇게 totalBottom과 totalTop를 구하게 되면 total[i]를 통해 결과값을 해석 할 수 있게된다.

소스 코드 : 

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 44 45 46 47 48 49 50 51 52 53 54 55

#include <iostream> #include <cstdio> #include <climits>   #define MAX 500002   using namespace std;   int totalBottom[MAX]; int totalTop[MAX]; int total[MAX]; int bottom[MAX]; int top[MAX];   int main()  {     int n, h;     int min = INT_MAX;     int count = 1;       scanf("%d %d", &n, &h);       for (int i = 0; i < n / 2; i++)      {         int bVal, tVal;         scanf("%d %d", &bVal, &tVal);           top[tVal]++;         bottom[bVal]++;     }       // Prefix Sum     for (int i = h; i >= 1; i--)     {         totalBottom[i] = bottom[i] + totalBottom[i + 1];         totalTop[i] = top[i] + totalTop[i + 1];     }       for (int i = 1; i <= h; i++)      {         // 길이 i의 석순을 파괴할때 파괴되는 모든 종유석과 석순의 수 계산         total[i] = totalBottom[i] + totalTop[h - i + 1];           // min과 count를 찾기위한 과정         if (total[i] <= min)              total[i] == min ? count++ : count = 1, min = total[i];     }       printf("%d %d\n", min, count);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus