[JAVA]伯俊S 12293硬貨1

7653 ワード
テキストリンク
出典:百駿オンライン阻止
https://www.acmicpc.net/problem/2293

問題を解く


これはDPを用いて解く方法である.
まず最初のコインで1~Kの数を表します.コインは1枚しか使わないので、状況の数は1になります.
次に2番目のコインを一緒に使う場合を求めます.
例を見てみましょう
1元2元5元3コインがあります.
1元しか使わない場合は
	 0 1 2 3 4 5 6 7 8 9 10
1원	 1 1 1 1 1 1 1 1 1 1 1
2元を同時に使うと
	 0 1 2 3 4 5 6 7 8 9 10
1원	 1 1 1 1 1 1 1 1 1 1 1
2원	 1 1 2 2 3 3 4 4 5 5 6
3元作成時の数(1元しか作成できない場合)+(2元使用時の数)
DPで表す場合は、DP[3]=DP[3]+DP[3-2]で表すことができる.
(1が3を作成する場合)+(1が1を作成する場合は2円玉を追加=1が1を作成)
コインをもう1枚追加します
3元作成時の数字は(1元、2元の数字)+(コイン使用時の数字)
DPの勉強を続けます...

正しいコード

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] dp = new int[15000];
		int[] arr = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		dp[0] = 1;
		for(int i = 0; i < N; i++) {
			for(int j = arr[i]; j <= K; j++) {
				dp[j] = dp[j] + dp[j - arr[i]]; 
			}
		}
		System.out.println(dp[K]);
	}
バックアップ1260 DFSとBFS
[TIL]21.05.20