BoJ 6159 - Costume Party [with Python / 문제 한국어로 번역]

📍 문제

오늘은 할로윈입니다!
농부 존은 소들을 데리고 할로윈 코스튬 파티에 가려고 합니다.
그러나 불행하게도 그에게는 의상이 하나 밖에 없습니다.
이 의상은 길이가 $S$ (1 <= $S$ <= 1,000,000) 인 두 마리의 소에 딱 맞습니다.
존은 $N$마리의 소를 가지고 있으며,
각각의 소 $i$는 길이가 $L_i$ (1 <= L_i <= 1,000,000) 입니다. 두 마리의 소가 의상에 맞으려면 그들의 길이 합이 의상의 길이를 초과하지 않아야 합니다.
존은 두 마리의 각각 다른 소들로, 과연 몇 쌍의 소가 이 의상에 맞을지 알고 싶어합니다!

📍 아이디어

단순 투 포인터 문제라기에는 약간의 변형이 있다.

초과하지 않는 케이스라면 모두 카운팅을 해주어야 하는데,
이 때 소들은 모두 길이 순으로 정렬된 상태이므로 그 카운팅 된 인덱스 사이의 모든 케이스 역시 문제의 조건을 만족하므로 계산을 해줘야 한다.

영어 문제 + 투 포인터 알고리즘 약간 번형해서
실버5 보다는 실버 4에 가깝지 않나 싶었으나,

이거 브루트 포스로도 풀 수 있어서 실버5에 배치한 듯 싶다.

📍 제출 코드

import sys

n, s = map(int, sys.stdin.readline().rstrip().split())
cnt = 0

cow = []

for i in range(n):
  cow.append(int(sys.stdin.readline().rstrip()))

cow.sort()

start = 0
end = len(cow)-1

while start < end:
  if cow[start] + cow[end] > s :
    end -= 1
  
  else:
    cnt += end - start
    start += 1

print(cnt)