[DP]문제#12.동전1

2293번: 동전 1 (acmicpc.net)

​

 

import java.util.Scanner;
public class DP5 {
	
	static int N,k;
	static int[]d;
	static int[]p;
	static int coin;
	
	public static void main(String[] args) {
		
	
		Scanner in=new Scanner(System.in);
		N=in.nextInt();
		k=in.nextInt();
		
		p=new int[N];
		d=new int[k+1];
		
		for(int i=0;i<N;i++) {
			p[i]=in.nextInt();
		}
		
		for(int i=0;i<N;i++) {
			coin=p[i]; d[coin]+=1;
			for(int j=coin+1;j<=k;j++) {
				if(d[j-coin]==0) continue;
				else
					d[j]=d[j-coin]*2;
			}
		}
		
		in.close();
		System.out.println(d[k]);
	}
}