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

3020번: 개똥벌레

 

풀이를 떠올리기 어려운 문제였다.

 

 

top 배열과 bottom 배열의 의미

처음 input함수에서 종유석과 석순의 높이를 입력 받으며, 해당 구간에서 길이가 끝나는 종유석, 석순의 개수를 카운팅해준다.

높이가 7일 때,
ex) 석순 3이 입력되면 3번 구간의 장애물이 하나 생겼음을 알 수 있다.
ex) 종유석 5가 입력되면 3번 구간의 장애물이 하나 생겼음을 알 수 있다. (7 - 5 + 1)

 

입력이 끝나면 모든 구간에 있는 장애물의 개수를 누적합으로 계산해 준다.

좌측 1,2,3,4,5,6,7은 높이에 따른 구간을 나타내었다.

이제 top과 bottom배열의 의미가 변하게 된다.

이전에는 top[index]의 index구간에서 끝나는 종유석, 석순의 길이를 저장했다면,

누적합을 계산하게 되면 index구간에 만나는 종유석, 석순의 장애물 개수가 저장된다.

 

 

종유석이 끝나는 구간을 초록색, 석순이 끝나는 구간을 파란색으로 칠했다.

 

석순부터 살펴보자

석순은 H구간부터 내려오면서 누적합을 계산해준다.

윗 구간일 수록 통과할 수 있는 장애물의 수가 줄어들고, 아랫 구간으로 갈 수록 윗 구간에서의 길이가 누적되어 걸리는 장애물의 수가 증가하게 된다.

 

종유석은 반대로 1구간부터 올라가면서 누적합을 계산해준다.

윗 구간으로 갈 수록 장애물의 개수가 증가하기 때문이다.

 

종유석과 석순의 구간별 장애물 개수를 구했으니 전체 장애물 개수는 둘을 합해서 계산하면 된다.

 

이제부터는 직관적으로 풀이가 가능하다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e13+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, H;
int top[500001];
int bottom[500001];
 
void input(){
    cin >> N >> H;
    int h;
    for(int i = 0; i < N; i++){
        cin >> h;
        // 석순
        if(i % 2 == 0) bottom[h]++;
        // 종유석
        else top[H - h + 1]++;
    }
}
 
void solve(){
    for(int i = 1; i <= H; i++){
        top[i] += top[i-1];
        bottom[H-i] += bottom[H-i+1];
    }
    
    ll ans = INF;
    int cnt = 0;
    for(int i = 1; i <= H; i++){
        if(top[i] + bottom[i] < ans){
            cnt = 1;
            ans = top[i] + bottom[i];
        }
        else if(top[i] + bottom[i] == ans){
            cnt++;
        }
    }
    
    cout << ans << " " << cnt;
}
 
int main(){
    input();
    solve();
    
    return 0;
}