취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26091번 문제인 현대모비스 소프트웨어 아카데미이다.
문제는 아래 링크를 확인하자.

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

주어진 학회원들로 $K$팀을 구성할 수 있는 상황을 생각해보자. 만약 능력치가 가장 높은 $K$명 중 어떤 사람이 $K$팀 구성에 포함되어 있지 않은 경우 그보다 작은 능력치를 가진 두 명으로 구성된 팀이 항상 존재하며, 해당 팀의 한 사람을 능력치가 높은 사람으로 교체해도 $K$팀을 항상 구성할 수 있음을 알 수 있다. 따라서 $K$팀을 구성할 수 있다면 능력치가 가장 높은 $K$명이 모두 포함된 팀 구성이 항상 존재함을 알 수 있다.

비슷한 방법으로, 어떤 $2K$명을 이용한 팀 구성이 존재할 경우 능력치가 가장 낮은 학회원과 가장 높은 학회원을 서로 한 팀으로 묶는 것을 반복해도 팀 구성이 제대로 됨을 증명할 수 있다. (부등식을 잘 세워보자.)

따라서, 가장 능력치가 높은 사람부터 가능한 가장 낮은 능력치를 가진(그래도 능력치의 합이 $M$ 이상은 되는) 학회원과 함께 팀으로 묶는 것을 반복하는 것으로 가장 많은 팀을 구성하는 하나의 경우를 얻을 수 있다.

이를 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, L, R, ans;
int A[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);

	L = 0, R = N - 1;
	while (L < R) {
		if (A[L] + A[R] >= M) L++, R--, ans++;
		else L++;
	}

	cout << ans;
}