[실버 3] 백준 28353 - 고양이 카페 (파이썬)

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

풀이

• 고양이들의 체중 리스트가 주어지고,
• 두 마리 고양이를 묶을 때, 체중 합이 K 이하이면 1쌍으로 만든다.
• 최대 몇 쌍을 만들 수 있는지를 구하는 문제.

A.sort()

체중을 오름차순으로 정렬한다. 가장 가벼운 고양이와 가장 무거운 고양이를 매칭해서 최대한 많이 쌍을 만들려고 하기 때문이다.

투 포인터는 다음과 같이 준비한다.

start, end = 0, N - 1
count = 0

start는 제일 가벼운 고양이를 가리키며 왼쪽 포인터를 의미한다.

end는 제일 무거운 고양이를 가리키며 오른쪽 포인터를 의미한다.

count는 만든 쌍의 수를 나타낸다.

while start < end:
    if A[start] + A[end] <= K:
        count += 1
        start += 1
        end -= 1
    else:
        end -= 1

두 고양이의 체중 합 A[start] + A[end]를 확인하여, 합이 K 이하이면, 쌍을 만들 수 있으니까, count += 1하고 둘 다 포인터를 움직인다.

합이 K 초과이면 제일 무거운 고양이를 뺴야하니까, end -= 1만 진행한다.

else 에서 start += 1을 하면 안되는 이유는, start쪽 고양이는 여전히 쌍을 지을 수 있는데 기회를 날려버릴수 있기 때문이다.

중요!

코드

# 백준 28353 - 고양이 카페
# 분류 : 투포인터

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
start, end = 0, N - 1

count = 0
while start < end :
    if A[start] + A[end] <= K :
        count += 1
        start += 1
        end -= 1
    else :
        end -= 1

print(count)