[백준][3020번][정렬] 개똥벌레

개똥벌레

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

<코드>

#include <stdio.h>
#include <climits>
using namespace std;
int totaldown[500002] = {};
int totalup[500002] = {};
int total[500002] = {};
int down[500002] = {};
int up[500002] = {};
int main(void){
 
    int N, H;
    int upMax = 0;
    int downMax = 0;
    int min = INT_MAX;
    int count = 1;
    scanf("%d %d", &N, &H);
 
    for (int i = 0; i < N / 2; i++){
        int upS, downS;
        scanf("%d %d", &downS, &upS);
        up[upS]++;
        down[downS]++;
        if (upMax < upS)
            upMax = upS;
        if (downMax < downS)
            downMax = downS;
    }
    
    for (int i = downMax; i >= 1; i--)
        totaldown[i] = down[i] + totaldown[i + 1];
    for (int i = upMax; i >= 1; i--)
        totalup[i] = up[i] + totalup[i + 1];
 
    for (int i = 1; i <= H; i++){
 
        if (i == 1)
            total[i] = totaldown[1];
        else if (i == H)
            total[i] = totalup[1];
        else
            total[i] = totaldown[i] + totalup[H - i + 1];
 
        if (total[i] == min){
            count++;
        }
        else if (total[i]<min){
            count = 1;
            min = total[i];
        }
 
    }
 
    printf("%d %d\n", min, count);
 
    return 0;
}

<문제 푼 요령>

1. 이 문제는 종유석과 석순을 나누어서 생각하였다.

2. 여기서 중요한것은 석순이나 종유석이나 아래의 값이 위의값을 항상 포함하고있는 것이다. 즉 그걸 이용하여서 각 개수를 카운트 한 후 

3. 그 카운트한 개수를 가지고 모든 구간에 대한 파괴해야 할 값들을 total[i] 에 만들었다.

4. 그 후 그 중 최소와 개수만 구하면 정답이 나온다.