[BOJ] Costume Party 6159번 C++

 

 

문제

It's Halloween! Farmer John is taking the cows to a costume party, but unfortunately he only has one costume. The costume fits precisely two cows with a length of S (1 <= S <= 1,000,000). FJ has N cows (2 <= N <= 20,000) conveniently numbered 1..N; cow i has length L_i (1 <= L_i <= 1,000,000). Two cows can fit into the costume if the sum of their lengths is no greater than the length of the costume. FJ wants to know how many pairs of two distinct cows will fit into the costume.

입력

• Line 1: Two space-separated integers: N and S
• Lines 2..N+1: Line i+1 contains a single integer: L_i

출력

• Line 1: A single integer representing the number of pairs of cows FJ can choose. Note that the order of the two cows does not matter.

 

접근 방식

 

두개의 소를 골라 길이의 합이 S보다 작은지 확인하면 된다.

이때도 투 포인터를 이용해 구할 수 있다.

단, 소의 길이를 정렬 후 투 포인터를 활용해야 한다.

 

만약 소의 길이가 S보다 작고

1. en이 N-1이라면 st 포인터를 증가하고, en포인터를 st+1한 값을 가르키게 한다

2. en이 N-1이 아니라면 en포인터를 증가시켜준다.

 

S보다 크다면 st 포인터를 증가하고, en포인터를 st+1한 값을 가르키게 하면 된다

 

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    int N,S; cin>>N>>S;
    vector<int> v(N);
    for(int i=0; i<N; i++) cin>>v[i];

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

    int st = 0;
    int en = 1;
    int cnt = 0;

    while(st < en && en < N) {
        int len = v[st] + v[en];
        if(len <= S) {
            cnt++;
            if(en == N-1) {
                st++;
                en = st+1;
            }
            else en++;
        }else {
            st++;
            en = st+1;
        }
    }
    cout<<cnt;
}