[백준] 2293번 동전 1 (gold 5

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.valueOf(st.nextToken());
        int k=Integer.valueOf(st.nextToken());
        int[] num=new int[n];
        for(int i=0; i<n; i++){
            num[i]=Integer.valueOf(br.readLine());
        }
        Arrays.sort(num);
        int[] dp=new int[k+1];
        for(int i=num[0]; i<=k; i+=num[0]){
            dp[i]=1;
        }

        int pre=num[0];
        for(int i=1; i<n; i++){
            if(pre==num[i]){
                continue;
            }
            int temp=num[i];
            for(int j=1; j<=k; j++){
                if(j/temp==1 && j%temp==0){
                    dp[j]++;
                }
                if(dp[j]!=0 && j+temp<=k){
                    dp[j+temp]=dp[j+temp]+dp[j];
                }
            }
            pre=num[i];
        }

        bw.write(dp[k]+"");
        bw.flush();

    }
}