[ BOJ 백준 3020번 - 개똥벌레 ] 해설 및 코드

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

 

목적

1에서 H의 높이로 동굴을 일직선으로 통과하는 동안에, 만나는 장애물의 최소 개수와 그 때의 경로의 개수를 구하자.

접근법

1. 분류는 이분탐색이다. 풀이는 누적합이다. 이유는 더 쉽고 빠르기 때문이다.

 

#include<iostream>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int s[500001] = { 0, };
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int n, h; cin >> n >> h; 
    n /= 2;
    
    f(i, 0, n) {
        int a, b; cin >> a >> b;
        --s[a]; ++s[h - b];
    }
 
    int mn = n, cnt = 1, curr=n;
    f(i, 1, h) {
        curr += s[i];
        if (curr == mn) ++cnt;
        else if (curr < mn) mn = curr, cnt = 1;
    }
    cout << mn << " " << cnt;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.