[백준/python3] 6159: Costume Party

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

6159번: Costume Party

---

알고리즘 분류

•  브루트포스 알고리즘
• 정렬
• 두 포인터

문제

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.

예제 입출력

풀이

전형적인 투포인터를 이용하여 풀 수 있는 문제이다. 다만 정렬이 필요하다.

---

코드

import sys

N, S = map(int, sys.stdin.readline().rstrip().split())
cow_lengths = []

for _ in range(N):
    L_i = int(sys.stdin.readline().rstrip())
    cow_lengths.append(L_i)
    
cow_lengths.sort()
    
cnt = 0
l = 0
r = N - 1
    
while l < r:
    if cow_lengths[l] + cow_lengths[r] <= S:
        cnt += r - l
        l += 1
    else:
        r -= 1
print(cnt)