고양이 카페

면접 대비

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

요약

N마리 고양이의 무게와 한계 K가 주어질 때, 두 마리 무게의 합이 K 이하가 되도록 짝을 지어 만들 수 있는 최대 짝의 수를 구한다.

난이도: 보통10점 중 5점
유형: 투 포인터, 정렬, 그리디, 배열
정답자: 아직 제출이 없습니다

문제

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

고양이 카페에는 $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
```