[BOJ/백준] 28353 - 고양이 카페

28353번: 고양이 카페

---

두 포인터

---

---

• 제목

고양이 카페

---

• 조건

시간 제한 : 2 초

메모리 제한 : 1024 MB 

---

• 문제

찬우는 친구들과 고양이 카페에 가려 한다.

고양이 카페에는 N마리의 고양이가 있다. i번째 고양이의 무게는 w_i이다. 찬우와 친구들은 모두 고양이를 사랑하기 때문에 무릎 위에 고양이를 정확히 2$2$마리 데리고 있으면 행복해진다. 하지만 허약한 찬우와 친구들은 데리고 있는 두 고양이의 무게의 합이 K를 넘는다면 버티지 못할 것이다.

각 고양이의 무게와 한 명이 버틸 수 있는 최대 무게 K가 주어질 때 최대 몇 명이 행복해질 수 있는지 구해보자.

---

• 입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. (1≤N≤5000, 1≤K≤10^9)

둘째 줄에는 각 고양이의 무게를 의미하는 N개의 정수 1,2,⋯,w_1, w_2, ..., w_N이 공백으로 구분되어 주어진다. (1≤w_i≤K)

---

• 출력

행복해질 수 있는 사람의 수의 최댓값을 출력한다.

---

예제 입력1	예제 출력1
5 20 8 16 11 2 4	2

예제 입력2	예제 출력2
6 10 9 5 6 7 4 3	2

예제 입력3	예제 출력3
4 100 100 99 98 97	0

---

N, K = map(int, input().split())
num = sorted(list(map(int, input().split())))
ans = 0
for i in range(N-1,-1,-1):
    if num[i] + num[0] <= K:
        l = 0
        r = i
        while l < r:
            if num[l] + num[r] <= K:
                ans += 1
                l += 1
                r -= 1
            else:
                r -= 1
        break
print(ans)