백준 28353 고양이 카페 Python: 정렬과 투 포인터의 그리디 증명

백준 28353번 고양이 카페는 고양이 두 마리의 무게 합이 K를 넘지 않도록 짝을 만들 때, 행복해질 수 있는 사람 수를 최대로 만드는 문제다. 고양이 한 마리는 한 번만 선택할 수 있고, 한 사람은 정확히 두 마리를 무릎에 올린다.

입력 범위는 N ≤ 5,000, K ≤ 10^9다. 모든 짝을 확인하면 O(N²)이므로 제한 안에 안정적으로 들어오기 어렵다. 무게를 정렬한 뒤 가장 가벼운 고양이와 가장 무거운 고양이를 보는 투 포인터로 O(N log N)에 풀 수 있다.

핵심 선택

무게를 오름차순으로 정렬하고 양 끝을 가리킨다.

가벼움                                  무거움
  ↓                                       ↓
[ 2, 4, 8, 11, 16 ]    K = 20
  L               R

두 무게의 합에 따라 선택은 둘 중 하나다.

• weight[L] + weight[R] > K: 가장 무거운 고양이는 누구와도 짝을 만들 수 없다. R만 줄인다.
• weight[L] + weight[R] ≤ K: 두 고양이를 한 짝으로 확정하고 L과 R을 모두 이동한다.

두 번째 경우에 “가벼운 고양이는 다른 고양이와 짝지으면 더 많은 쌍을 만들 수 있지 않을까?”라는 의문이 생길 수 있다. 이 선택이 안전한 이유를 확인해야 그리디가 완성된다.

왜 가장 가벼운 고양이와 가장 무거운 고양이를 묶어도 되는가

현재 남은 고양이 가운데 가장 가벼운 무게를 s, 가장 무거운 무게를 h라고 하자.

s + h > K인 경우

s는 남은 고양이 중 가장 가볍다. 가장 가벼운 s와도 합이 한도를 넘는다면 h는 다른 어떤 고양이와도 짝이 될 수 없다.

따라서 h를 버리는 선택은 최적해의 쌍 수를 줄이지 않는다.

s + h ≤ K인 경우

s와 h는 실제로 짝이 될 수 있다. 이제 어떤 최적해를 하나 생각해 보자.

• 둘 다 짝이 없다면 (s, h)를 추가할 수 있으므로 기존 해는 최적이 아니다.
• 둘 중 하나만 다른 고양이와 짝이라면 그 짝을 (s, h)로 바꿔도 쌍 수는 같다.
• s가 x와, h가 y와 각각 짝이라면 (s, h)와 (x, y)로 바꿀 수 있다. x ≤ h이고 기존에 h + y ≤ K였으므로 x + y ≤ K도 성립한다.

즉, 최적해 중에는 항상 (s, h)를 포함하는 해가 하나 이상 존재한다. 그래서 합이 한도 안에 들어올 때 양 끝을 묶어도 최적성을 잃지 않는다.

Python 풀이

import sys

input = sys.stdin.readline

n, limit = map(int, input().split())
weights = list(map(int, input().split()))
weights.sort()

left = 0
right = n - 1
people = 0

while left < right:
    if weights[left] + weights[right] <= limit:
        people += 1
        left += 1
        right -= 1
    else:
        right -= 1

print(people)

people은 사용한 고양이 수가 아니라 만들어진 쌍의 수, 곧 행복해지는 사람 수다. 한 쌍을 만들 때마다 1을 더한다.

예제로 포인터 이동 따라가기

문제의 예제는 다음과 같다.

N = 5, K = 20
무게 = 8 16 11 2 4

정렬하면 2, 4, 8, 11, 16이다.

단계	확인한 두 무게	판단	누적 쌍
1	2 + 16 = 18	짝을 만들고 양쪽 이동	1
2	4 + 11 = 15	짝을 만들고 양쪽 이동	2
종료	고양이 8 한 마리 남음	두 마리가 아니므로 종료	2

정답은 2다.

복잡도와 구현 경계

• 정렬: O(N log N)
• 투 포인터 순회: O(N)
• 전체 시간 복잡도: O(N log N)
• 추가 공간: Python 정렬 구현과 입력 배열에 의존한다. 알고리즘 자체의 포인터 상태는 O(1)이다.

N이 홀수면 마지막에 고양이 한 마리가 남을 수 있다. 반복 조건을 left <= right가 아니라 left < right로 두면 한 마리를 자기 자신과 묶는 실수를 막을 수 있다.

투 포인터가 익숙하지 않다면 백준 3273 두 수의 합 풀이와 백준 2470 두 용액 풀이를 함께 보면, 정렬된 배열에서 양 끝을 움직이는 기준이 더 선명해진다.

참고 자료

• 백준 28353번 고양이 카페