본문 바로가기
알고리즘

[Java] 백준 2293번 동전 1 (Dynamic Programming)

by 태풍사랑 2020. 5. 8.

www.acmicpc.net/problem/2293

 

2293번: 동전 1

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

풀이


1원 = 1

2원 = 1 + 1 = 2

3원 = 1 + 1 + 1 = 2 + 1

4원 = 1 + 1 + 1 + 1 = 2 + 2

5원 = 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1

6원 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 2  ....

 

만약 5원을 구한다고 하면

- 4원에서 +1 -> 1가지

- 3원에서 +2 -> 2가지

- 0원에서 +5 -> 1가지  

=> 총 4가지

 

N번째 동전을 써서 K원을 만드는 경우의 수는 

 dp[i] += dp[i-coin[i]]

 

public class algo_2293_dp {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(), k = sc.nextInt(), coin;
		int[] dp = new int[k+1];
		
		dp[0] = 1;
		
		for(int i = 0; i<n; i++) {
			coin = sc.nextInt();
			for(int j = 1; j < k+1; j++) {
				if(j >= coin)
					dp[j] += dp[j-coin];
				}
		}
		System.out.println(dp[k]);
	}
}

댓글