R02202
예산에 가장 가까운 두 상품
실버 III레이팅
의견: 0
설명
가게에 \(N\)개의 상품이 있고 \(i\)번째 상품의 가격은 \(a_i\)이다.
손님은 서로 다른 두 상품을 골라 그 가격의 합이 예산 \(T\)에 최대한 가깝기를 원한다. 두 상품 가격의 합과 \(T\)의 차이(절댓값)가 최소가 되도록 골랐을 때, 그 최소 차이를 구하여라.
제약
\(2 \le N \le 2000\), \(1 \le a_i \le 10^9\), \(1 \le T \le 2 \cdot 10^9\)
입력 형식
첫째 줄에 상품 수 \(N\)과 예산 \(T\)가 주어진다.
둘째 줄에 \(N\)개의 가격 \(a_1, \dots, a_N\)이 주어진다.
출력 형식
두 상품 가격 합과 \(T\)의 차이의 최솟값(절댓값)을 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 40점 | \(2 \le N \le 300\) |
Subtask 2 | 60점 | 추가 제약이 없다. |
예제 1
입력
5 10
1 2 4 7 11
출력
1
설명
\(2+7=9\) 또는 \(4+7=11\)로 목표 \(10\)과의 차이가 \(1\)이 최소이다.
예제 2
입력
2 5
10 20
출력
25
설명
짝이 하나뿐이라 합 \(30\)과 목표 \(5\)의 차이 \(25\)가 답이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
예산에 가장 가까운 두 상품
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
예산에 가장 가까운 두 상품
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기