문제 1019 · 기초 4
예산 안의 두 개
투 포인터 · 정렬
테스트별 제한 2000ms · 브라우저 채점
문제
팀 회식비로 B원이 남았다. 편의점 진열대에 물건 N개가 있고 i번째 물건의 가격은 p_i 원이다. 서로 다른 물건 두 개를 골라 가격의 합이 B원 이하가 되는 방법이 몇 가지인지 세려 한다. 가격이 같더라도 진열대의 자리가 다르면 다른 물건이다. 두 물건을 고르는 순서는 따지지 않는다.
입력
첫째 줄에 N 과 B 가 주어진다. (1 ≤ N ≤ 50,000, 1 ≤ B ≤ 2,000,000) 둘째 줄에 가격 p_1 … p_N 이 주어진다. (1 ≤ p_i ≤ 1,000,000)
출력
방법의 수를 출력한다. 답이 32비트 정수 범위를 넘을 수 있다.
예제 입력 1
5 10 7 2 5 3 8
예제 출력 1
6
예제 입력 2
4 3 2 2 2 2
예제 출력 2
0
힌트 펼치기
- 모든 쌍을 확인하면 N² / 2 번, 최대 12억 번이 넘는다. 먼저 정렬하자.
- 정렬한 뒤 왼쪽 끝 i, 오른쪽 끝 j 에서 시작한다. p_i + p_j ≤ B 이면 i 와 짝지을 수 있는 것이 j − i 개다.
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.