이사 도우미 지우는 무게가 정해진 상자 \(N\) 개를 가지고 있다. 지우는 이 상자들 중 일부를 골라 두 개의 수레에 나눠 실으려 하는데, 두 수레에 실은 상자들의 무게 합이 정확히 목표 \(T\) 가 되도록 만들고 싶다.

상자를 어느 수레에 싣는지는 합에 영향을 주지 않으므로, 결국 문제는 고른 상자들의 무게 합이 정확히 \(T\) 가 되도록 부분집합을 고를 수 있는가로 귀결된다. 상자는 하나도 고르지 않아도 되고(\(T = 0\) 인 경우), 모두 골라도 된다. 단, 각 상자는 최대 한 번만 사용할 수 있다.

\(N\) 개의 상자 무게와 목표 \(T\) 가 주어질 때, 무게 합이 정확히 \(T\) 가 되도록 상자들의 부분집합을 고를 수 있으면 YES, 그렇지 않으면 NO 를 출력하는 프로그램을 작성하라.

\(1 \le N \le 1{,}000\)

\(0 \le T \le 1{,}000{,}000\)

\(1 \le w_i \le 1{,}000\)

첫째 줄에 상자의 개수 \(N\) 과 목표 무게 \(T\) 가 공백으로 구분되어 주어진다 (\(1 \le N \le 1{,}000\), \(0 \le T \le 1{,}000{,}000\)).

둘째 줄에 \(N\) 개의 상자 무게 \(w_1, w_2, \dots, w_N\) 이 공백으로 구분되어 주어진다 (\(1 \le w_i \le 1{,}000\)).

무게 합이 정확히 \(T\) 가 되는 상자들의 부분집합이 존재하면 YES 를, 존재하지 않으면 NO 를 한 줄에 출력한다.

riseoj 작성

출처 Original