[백준] 3020번 : 개똥벌레 - C++

백준 3020번 : 개똥벌레

등급 : Gold V

3020번: 개똥벌레 (acmicpc.net)

3020번: 개똥벌레

사용 알고리즘 : -

사용 자료구조 : Vector

 

이분 탐색이라고 쓰여있지만 딱히 이분 탐색 알고리즘을 사용하지 않아도 되는 문제이다.

첫 접근은 이중 for문으로 각 자리를 계산하는 방식으로 진행하였다. → TLE

때문에 석순과 종유석의 벡터를 각각 구현해주고, 각각의 for문을 누적 합으로 구현했다.

 

• Top vector : 종유석 지정 벡터. 
• Bottom vector : 석순 지정 벡터.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define INF 2e9

int n, h;
vector <int> top;
vector <int> bottom;
vector <int> ans;
// 종유석 벡터, 석순 벡터, 합 벡터 정의

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    cin >> n >> h;
    top.resize(h + 1, 0);
    bottom.resize(h + 1, 0);
    ans.resize(h + 1, 0);
    /* 각각의 벡터를 높이에 맞춰 크기 재설정. v[0]은 사용하지 않음.
       각 범위에서 몇 번 마주치는지를 저장할 벡터 */

    int a, b;
    for (int i = 0; i < n/2; i++)
    {
        cin >> a >> b;
        bottom[a]++;
        top[h + 1 - b]++;
    }
    /* i는 짝수개로 들어온다고 하였으므로 2로 나누고 순서대로 입력받아도 문제 없음.
       석순 - 종유석 순으로 입력받으므로 bottom과 top에 맞게 입력시켜줌.
       가장 긴 위치를 입력해줘야 하므로 종유석의 경우 b 대신 h + 1 - b를 입력하도록 함 */
    for (int i = 1; i < h; i++)
    {
        top[i + 1] += top[i];
    }
    // 종유석의 경우 위쪽으로 이어져있으므로, 아래에서 위쪽으로 누적합을 해준다
    for (int i = h - 1; i > 1; i--)
    {
        bottom[i - 1] += bottom[i];
    }
    // 석순의 경우 아래로 이어져 있으므로 위쪽에서 아래쪽으로 누적합을 해준다
    for (int i = 1; i <= h; i++)
    {
        ans[i] = top[i] + bottom[i];
    }

    ans[0] = INF;
    // 0번째 위치는 사용하지 않으므로 오름차순 정렬을 위해 0번째 벡터에 가장 큰 값을 넣어준다
    sort(ans.begin(), ans.end());

    cout << ans.front() << " " << upper_bound(ans.begin(), ans.end(), ans.front()) - lower_bound(ans.begin(), ans.end(), ans.front());
    // 가장 적게 부딪히는 횟수와 그런 장소가 몇 번 있는지 출력
}