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

최대한 많은 팀을 만들되, 각 팀의 능력치 합이 최소값 M 이상이 되도록하는 문제이다.

---

 

투 포인터를 이용하면 간단하게 풀린다.

로직은 다음과 같다.

두 개의 포인터 low와 high를 사용하여 배열의 양 끝에서부터 탐색을 시작한다.

 

- low 포인터는 배열의 시작에서, high 포인터는 배열의 끝에서 시작한다.

 

- 현재 low와 high가 가리키는 두 원소의 합이 m 이상이면, 해당 팀을 구성할 수 있으므로 팀의 수를 증가시키고 포인터를 이동시킨다.

 

- 현재 합이 m 미만이면, low 포인터를 오른쪽으로 이동시켜 합을 증가시킬 기회를 만든다.

 

- 이 과정을 low 포인터가 high 포인터와 같아지거나 넘을 때까지 반복한다.

 

<소스코드>

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, m;
int arr[100010];

int main()
{
    int i, j;
    scanf("%d %d", &n, &m);
    for(i=0;i<n;i++) scanf("%d", &arr[i]);
    sort(arr, arr + n);
    int high = n - 1, low = 0;
    int ans = 0;
    while(low < high) {
        int res = arr[low] + arr[high];
        if(res < m) {
            low++;
            continue;
        }
        ans++;
        high--;
        low++;
    }
    printf("%d", ans);
    return 0;
}

 

 

^^