백준 3020번 개똥벌레

문제 링크입니다: https://www.acmicpc.net/problem/3020

lower_bound와 upper_bound를 적절히 이용하면 쉽게 풀 수 있는 문제였습니다.

코드를 보면 금방 이해할 수 있을 것입니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, H;

        cin >> N >> H;

 

        vector<int> bottom(N/2), top(N/2);

        for (int i = 0; i < N/2; i++)

                 cin >> bottom[i] >> top[i];

 

        sort(bottom.begin(), bottom.end());

        sort(top.begin(), top.end());

 

        int result = INF;

        int cnt = 1;

        for (int i = 1; i <= H; i++)

        {

                 //해당 높이에 겹치는 석순

                 int temp = bottom.size() - (lower_bound(bottom.begin(), bottom.end(), i) - bottom.begin());

                 //해당 높이에 겹치는 종유석

                 temp += top.size() - (upper_bound(top.begin(), top.end(), H - i) - top.begin());

 

                 if (result == temp)

                         cnt++;

                 else if (result > temp)

                 {

                         result = temp;

                         cnt = 1;

                 }

        }

        cout << result << " " << cnt << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~