고양이 카페

면접 대비

시간 제한2초메모리 제한1024 MB

요약

고양이 N마리를 두 마리씩 짝지어 무게 합이 K 이하가 되게 할 때, 만들 수 있는 최대 짝의 수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 정렬, 투 포인터, 그리디
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

첫째 줄에 정수 $N$ 과 $K$ 가 공백으로 구분되어 주어진다. ( $1 \leq N \leq 5\,000$ ; $1 \leq K \leq 10^9$ )

둘째 줄에는 각 고양이의 무게를 의미하는 $N$ 개의 정수 $w\_1, w\_2, \dotsm, w\_N$ 이 공백으로 구분되어 주어진다. ( $1 \leq w\_i \leq K$ )

출력

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

예제3

예제 1
입력
```
5 20
8 16 11 2 4
```
예상 출력
```
2
```
예제 2
입력
```
6 10
9 5 6 7 4 3
```
예상 출력
```
2
```
예제 3
입력
```
4 100
100 99 98 97
```
예상 출력
```
0
```