줄자 나누기 > 문제은행



1478 : 줄자 나누기

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
15 회   
시도횟수
126 회   

문제

N(1≤N≤2,000)개의 줄자가 주어졌을 때, 줄자들을 몇개를 골라서 일렬로 늘어놓았을 경우에의 길이가 정수 F(1≤F≤1,000)로 나눌 수 있는 경우가 몇가지인지 알아보는 프로그램을 작성하자.

 

줄자의 길이는 양의 정수이며 1이상 10,000이하다.

 

만약 1, 2, 2, 8의 줄자가 주어졌을 때 F=5일 경우에는, 다음과 같은 경우가 가능하다.
{ 1, 2, 2 }, { 2, 8 }, { 2, 8 }
{ 2, 8 }의 경우 2의 길이의 줄자가 2개 있기 때문에 두 가지 경우가 생긴다.


입력형식

입력의 첫 번째 줄에는 N과 F가 입력된다.그 다음 줄부터 N개의 줄에는 줄자의 길이가 한 줄에 하나씩 입력된다.

출력형식

F로 나눠질 수 있는 줄자들의 길이의 합의 경우의 수를 100,000,000로 나눈 나머지를 출력한다.

입력 예

4 5
1
2
8
2

출력 예

3

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP