[BOJ/백준] 6159 - Costume Party (Python)

문제

문제링크

N마리의 소가 있을 때, 그 중 두 소의 길이의 합이 S보다 작거나 같을 때의 pair 수를 구하라.

 

풀이

리스트에 입력받은 소의 길이를 정렬한다.

양 끝에서 두 소를 선택하고 무게 합이 S 이하이면 left에 해당하는 소에 대해 right 소까지 모든 쌍이 조건을 만족하므로

right-left 만큼 더하고 left를 1 증가시켜 다음 left 소에 대한 쌍을 확인한다.

만약 S보다 크다면 right를 1 감소시켜 위 과정을 left<right일 때까지 반복한다.

 

코드

N, S=map(int, input().split())

cows=[int(input()) for _ in range(N)]
cows.sort()

fit=0
left, right=0, N-1
while left<right:
  if cows[left]+cows[right]<=S: 
    fit+=right-left
    left+=1
  else: right-=1

print(fit)