[백준] 3020 개똥벌레 prefix sum(누적합)

문제 :

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

3020번: 개똥벌레

 

분석 :

1. 석순과 종유석의 구분은 짝수인지 홀수인지다. 따라서 개똥벌레가 높이 1인 곳을 지난다면 종유석은 1인 높이, 석순은 H -1 인 높이를 동시에 지난다고 생각하면 된다.

2. 석순끼리의 (또는 종유석끼리의) 순서 바뀜은 상관이 없다. 개똥벌레는 N 길이를 통과하야 하기 때문이다. 석순의 길이만큼 가진 석순 개수를 배열에 저장한다. (종유석도 똑같다)

3. 높이가 H일때 개똥벌레는 종유석의 H 높이만을 지나간다. H-1일때는 H-1 높이인 종유석 + H 높이인 종유석을 지나간다. 마찬가지로 H-2일때 ==> H-2 높이 종유석 + H-1 높이 종유석 + H 높이 종유석을 지나간다. 누적합을 적용하면 될거 같다.

4. 석순과 종유석을 동시에 지나가므로 sum 배열에 i높이 석순 + H-i 높이 종유석을 더해 개똥벌레가 지나갈 총 장애물을 저장한다.

 

c++ 코드 :

//
//  3020_ firefly.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/02/21.
//

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;
int N, H, h;
long long mite[5000001]; //석순
long long tite[5000001]; //종유석
long long sum[5000001];

int main(){
    cin >> N >> H;
    memset(mite, 0, sizeof(mite));
    memset(tite, 0, sizeof(tite));
    memset(sum, 0, sizeof(sum));
    
    for(int i = 1; i <= N; i++){
        cin >> h;
        if(i % 2 == 1){ // 석순
            mite[h]++; //h 높이인 개수
        }else{
            tite[h]++;
        }
    }
    
    for(int i = H - 2; i >= 1; i--){ // 누적합
        mite[i] += mite[i+1];
        tite[i] += tite[i+1];
    }
    
    for(int i = 1; i <= H; i++){
        sum[i] = mite[i] + tite[H + 1 - i]; // i 높이 석순 + H - i 높이 종유석
    }
    
    sort(sum+1, sum+H+1); // 1 ~ H
    
    int cnt = 0;
    int target = sum[1];
    for(int i = 1; i <= H; i++){
        if(sum[i] == target){
            cnt++;
        }
    }

    
    cout << target << " " << cnt <<'\n';
    
    return 0;
}