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

 

문제

3020번: 개똥벌레

 

 

 

해결 방법

1. 석순의 길이는 입력받는 값 그대로 stalagmite 배열에 저장

2. 종유석의 길이는 바닥과 종유석까지의 거리로 변환(동굴의 높이 - 종유석 길이)하여 stalactite 배열에 저장

3. stalagmite, stalactite 배열을 각각 오름차순 정렬

4. 1번째 구간부터 동굴의 높이와 같은 구간까지 탐색하며 해당 구간에서 석순과 종유석과 각각 몇 개씩 만나는지 계산!

이때 lower_bound() 함수를 사용하여 만나는 개수를 바로 탐색할 수 있는데,

 

 

예를 들어 문제의 예시와 같은 입력이 주어지고 현재 2번째 구간을 탐색하고 있다고 하자.

석순의 길이를 저장한 stalagmite 배열에서 lower_bound() 함수를 쓰게 되면

key 값 보다 크거나 같은 값이 저장된 iterator의 위치를 반환하므로 1을 반환한다. 

1번 인덱스부터 이후로는 구간과 석순이 만나므로

개똥벌레가 부쉬어야 하는 석순의 개수는 (전체 석순의 개수 - 1) = 6개이다.

 

종유석의 길이를 저장한 stalactite 배열에서 lower_bound() 함수를 쓰게 되면 2를 반환하고,

2번 인덱스부터 이후로는 구간과 종유석이 만나지 않으므로

개똥벌레가 부쉬어야 하는 종유석의 개수는 2개이다.

 

이렇게 각 구간마다 개똥벌레가 부쉬어야 하는 석순과 종유석의 개수 찾은 뒤

이 중에 최솟값을 답으로 출력하면 된다.

 

 

lower_bound() 함수에 대한 자세한 설명과 주의사항은 아래 링크를 통해서 확인하자.

[2352] 반도체 설계

 

 

 

내 코드(C++)

// [3020] 개똥벌레
// https://www.acmicpc.net/problem/3020
// 이분 탐색, 정렬

#include <vector>
#include <algorithm> // lower_bound()
#include <cstdio>
using namespace std;

int main(void)
{
    /* 
    cnt = 각 구간마다 개똥벌레가 파괴해야 하는 석순 & 종유석 개수
    section = 개똥벌레가 지나갈 구간
    min = 개똥벌레가 파괴하는 석순 & 종유석 개수의 최솟값
    ans = min값을 가지는 구간의 개수
    */
    
    int n, h, tmp1, tmp2, cnt = 0, min, section, ans = 1;
    vector <int> stalagmite, stalacitite; // 석순, 종유석
    scanf("%d %d", &n, &h);
    min = n;
    
    for(int i = 0 ; i < n/2 ; i++) {
        scanf("%d %d ", &tmp1, &tmp2);
        stalagmite.push_back(tmp1);
        stalactite.push_back(h - tmp2); // 바닥부터 종유석까지의 거리를 저장 
    }

    sort(stalagmite.begin(), stalagmite.end());
    sort(stalactite.begin(), stalacitite.end());

    for(int section = 1 ; section <= h ; section++) {
    
        // 석순과 구간이 만나는 최소 인덱스 탐색
        int it = lower_bound(stalagmite.begin(), stalagmite.end(), section) - stalagmite.begin();
        
        // 인덱스 it부터 석순의 끝 인덱스까지는 구간과 모두 만남 
        cnt = n/2 - it;

        // 종유석과 구간이 만나는 최소 인덱스 탐색
        it = lower_bound(stalactite.begin(), stalactite.end(), section) - stalactite.begin();
        
        /* 종유석 벡터 : (바닥 ~ 종유석) 거리
           -> 구간과 stalactite 벡터가 만난다면 종유석과 구간은 만나지 않는다는 뜻
           -> 처음부터 인덱스 it 직전까지만 종유석과 구간이 만남 
        */
        
        cnt += it;

        if(cnt < min) {
            min = cnt;
            ans = 1;
        }  
        
        else if(cnt == min) {
            ans++;
        }
    }
    
    printf("%d %d\n", min, ans);
}