저울 위의 두 상자
실버 III의견: 0
택배 기사 윤호의 트럭에는 소포 상자 \(N\)개가 있고, \(i\)번째 상자의 무게는 \(w_i\)이다.
두 상자를 하나의 묶음으로 포장해 보내면 배송비가 할인되는데, 포장 기계의 한계 때문에 두 상자 무게의 합이 \(S\) 이하인 경우에만 묶을 수 있다.
묶을 수 있는 서로 다른 상자 쌍이 모두 몇 가지인지 구하여라. 쌍의 순서는 구분하지 않는다.
- \(2 \le N \le 200\,000\)
- \(1 \le w_i \le 10^9\)
- \(1 \le S \le 2 \cdot 10^9\)
첫째 줄에 상자의 수 \(N\)과 무게 한도 \(S\)가 공백으로 구분되어 주어진다.
둘째 줄에 상자의 무게 \(w_1, w_2, \dots, w_N\)이 공백으로 구분되어 주어진다.
무게 합이 \(S\) 이하인 상자 쌍의 개수를 출력한다.
4 5
1 2 3 4
4
합이 \(5\) 이하인 쌍은 \((1,2), (1,3), (1,4), (2,3)\)의 \(4\)가지이다.
2 9
5 5
0
유일한 쌍 \((5,5)\)의 합이 \(10 > 9\)이므로 가능한 묶음이 없다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
저울 위의 두 상자
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
저울 위의 두 상자