[BOJ 3020] 개똥벌레

3020번: 개똥벌레

1. 문제

 

예제 1을 그림으로 표현하면 다음과 같다.

개똥벌레가 높이가 3.5, 5.5, 6.5인 지점을 지날 때 파괴해야 하는 장애물이 2개로 이 때가 최소가 된다.

 

2. 구현 아이디어

• 석순과 종유석을 따로 저장한다
  • 종유석은 (높이)-(장애물의 길이)로 저장한다

• 반복문을 통해 모든 지점에 대해 각 위치에 대해 파괴해야 할 장애물의 위치를 센다
  • 편의상 0.5, 1.5처럼 X.5 지점이라고 생각하자
  • 이분 탐색을 사용하여 나는 지점(target)의 위치를 확인하고, 그 이상(이하)인 수들의 개수를 세면 된다
• 이분 탐색을 진행하기 위해 배열을 오름차순으로 정렬해야 한다
• 석순 → target의 위치보다 오른쪽에 있는(= 더 큰) 원소들의 개수를 센다 → v.size() - target의 index

• 종유석 → target의 위치보다 왼쪽에 있는(= 더 작은) 원소들의 개수를 센다 → target의 index

 

3. lower_bound()와 upper_bound()

이분탐색 도식화

C++에서는 이분 탐색으로 원소를 탐색하는 lower_bound()와 upper_bound() 함수를 제공하고 있다.

해당 함수를 사용하여 로직을 직접 구현하지 않고 이분탐색을 활용할 수 있다.

 

• lower_bound() - 찾고자 하는 target과 같거나 큰 값이 처음 나온 위치
• upper_bound() - 찾고자 하는 target보다 큰 값이 처음 나온 위치

 

target이 배열 범위 안에 있을 경우

target이 배열 범위 안에 없을 경우

4. 전체 코드 - 맞았습니다 !!

#include <bits/stdc++.h>

using namespace std;

int n, h; // 동굴의 길이, 높이
int k; // 장애물의 크기

vector<int> v1, v2; // 종유석, 석순

pair<int, int> p;
int ret1, ret2, ret;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> h;
    p = {n, 1}; // 장애물의 최솟값, 구간의 수

    for (int i = 0; i < n; ++i) {
        cin >> k;
        // 석순과 종유석이 번갈아 나오므로 짝수, 홀수 여부로 나누어 배열에 저장
        if (i%2 == 0) v1.push_back(k); // 석순
        else v2.push_back(h-k); // 종유석
    }
    // 이분 탐색을 위한 정렬
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    for (int i = 0; i < h; ++i) {
        ret1 = v1.size() - (upper_bound(v1.begin(), v1.end(), 0.5+i) - v1.begin()); // 석순
        ret2 = upper_bound(v2.begin(), v2.end(), 0.5+i) - v2.begin(); // 종유석
        // 총 장애물 개수
        ret = ret1 + ret2;

        // 장애물이 더 적은 구간을 발견할 경우 갱신
        if (ret < p.first) p = {ret, 1};
            // 구간의 개수 count
        else if (ret == p.first) p.second ++;
    }

    cout << p.first << " " << p.second << "\n";

    return 0;
}