[BOJ/Silver 1] 백준 26091 현대모비스 소프트웨어 아카데미(C++)

문제 링크

https://www.acmicpc.net/problem/26091

26091번: 현대모비스 소프트웨어 아카데미

 

문제

현대모비스는 글로벌 자동차 부품 기업으로 자율주행, 커넥티비티, 전동화 분야에 역량을 집중해 스마트 모빌리티 시대를 선도하고 있는 기업입니다.

현대모비스는 소프트웨어 생태계 조성을 위해 소프트웨어 아카데미를 운영하고 있으며, 내부적으로는 연구원들의 소프트웨어 직무교육 이수를 통해 우수인재를 육성하고, 대외적으로는 채용 연계형 프로그램을 운영하여 취업 준비생들에게 소프트웨어 전문 교육을 무상으로 제공하고, 더 나아가 우수 이수자들을 채용하고 있습니다.

 

현대모비스에서 소프트웨어 아카데미 견학생을 모집한다고 한다. 이번 견학 활동은 모두 팀 단위로 진행되며 아래 두 조건을 모두 만족하는 팀만 소프트웨어 아카데미를 견학할 수 있다.

• 팀원이 두 명이다.
• 팀의 능력치가 M 이상이다. 팀의 능력치는 모든 팀원의 능력치를 합한 값이다.

 

Sogang ICPC Team 학회원 N명이 견학을 희망한다. 학회장 동건이는 N명으로 최대한 많은 팀을 만들어 견학을 보내고 싶다. 동건이가 최대 몇 팀이나 견학 보낼 수 있을지 구해보자.

 

입력

첫째 줄에 견학을 희망하는 학회원의 수 N과 견학하는 팀의 최소 능력치를 나타내는 정수 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 10^9)

둘째 줄에 학회원 N명의 능력치를 나타내는 N개의 정수 a1, a2, ⋯, aN이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 10^9)

 

출력

첫째 줄에 동건이가 견학 보낼 수 있는 최대 팀 수를 출력한다.

 

예제 입력 1

6 10
3 5 7 3 5 6

예제 출력 1

2

예제 입력 2

1 10
100

예제 출력 2

0

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

학회원 N명을 능력치를 기준으로 오름차순 정렬한다.

그리고 두 포인터를 사용하여 0번째 학회원과 N - 1번째 학회원의 능력치의 합을 따진다. 두 포인터를 사용함으로써 능력치의 총합이 M 이상인 팀을 최대한 많이 만들 수 있다.

두 학회원의 능력치의 합이 M 이상이면 왼쪽 포인터와 오른쪽 포인터를 하나씩 이동시키고, 그게 아니라면 능력치의 합을 올려야 하기 때문에 왼쪽 포인터만 이동시킨다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, L, R;
vector<int> Vec;
int Answer;

void input() {
    cin >> N >> M;
    Vec.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> Vec[i];
    }
}

void settings() {
    sort(Vec.begin(), Vec.end());
    R = N - 1;

    while (L < R) {
        int First = Vec[L];
        int Last = Vec[R];
        if (First + Last >= M) {
            Answer++;
            R--;
        }
        L++;
    };
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}