백준 26091 현대모비스 소프트웨어 아카데미 / C++

문제 : 26091

풀이 point

학생 수(N)의 범위가 $1<= N <= 10^5$
$N^2$ 완전 탐색은 불가능
-> 대신 학생들의 순서를 유지할 필요가 없고, 두 학생의 능력치 합이 주어진 능력치 보다 크면 됨
-> 최대한 많은 팀을 만드는 것이 목적이기 때문에 가장 큰 능력치를 가진 학생과 가장 작은 능력치를 가진 학생을 팀으로 만들어야함

풀이 순서

1. 정렬을 한다(가장 작은 것이 앞, 가장 큰 것이 뒤)
2. 가장 작은 능력치와 가장 큰 능력치를 더해본 후 주어진 능력치보다 크면 팀 성사
3. 그렇지 않으면 가장 작은 능력치보다 한칸 더 큰 능력치와 비교

코드

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

int N, M;
std::vector<long long> vec(100001, 0);

void solve(){
    sort(vec.begin(), vec.begin()+N);
    int start{0}, result{0}; int end{N-1};
    while(start < end){ //start와 end가 만나기 직전
        if(vec[start] + vec[end] >= M){ //주어진 능력치 보다 큰가?
            ++result;
            ++start; //start는 오른쪽
            --end; //end는 왼쪽으로 이동
            //start와 end가 가까워짐
        }
        else{
            ++start; //start만 오른쪽으로 이동(주어진 능력치보다 크지 않음)
        }
    }
    std::cout << result;
}


int main(){

    std::cin >> N >> M;
    for(auto i{0}; i<N; ++i){
        std::cin >> vec[i];
    }

    solve();
    
    return 0;
}