[JAVA] 백준 2293번 : 동전 1

 

---

 

• 생각

1. 점화식은 어떻게 생각해야될 지 감이 오지 않는다..

 

 

• 코드

정답 코드 : 링크를 보고 이해하여서 코드를 작성했다. 다시 풀어봐야할 것 같음.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Algorithm {
	static int N, S;
	static int[] coin, dp;

	public static void main(String[] args) throws Exception {
		SetData();
		dp();
		System.out.println(dp[S]);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());

		coin = new int[101]; 
		dp = new int[10001];

		for (int i = 1; i <= N; i++)
			coin[i] = Integer.parseInt(br.readLine());

		dp[0] = 1; 
	}

	private static void dp() {
		for (int i = 1; i <= N; i++) {
			for (int j = coin[i]; j <= S; j++) {
				dp[j] += dp[j - coin[i]];
			}
		}

	}
}