[백준] 2293 - 동전 1

[문제링크]

2293번: 동전 1

 

0. 동전으로 특정 액수를 만들어야하는 DP 문제

 

1. n-1번 동전까지 고려한 가짓수 정보가 있다면, n번 동전의 가짓수를 구할 수 있다

• 냅색 문제와 비슷하다

 

2. n-1번 동전까지의 정보가 있다면, X원짜리 n번 동전으로 k원을 만드는 가짓수는

• n번 동전 1개 선택 = n-1번 동전까지로 k-X를 만드는 가짓수
• n번 동전 2개 선택 = n-1번 동전까지로 k-2*X를 만드는 가짓수
• n번 동전 3개 선택 = n-1번 동전까지로 k-3*X를 만드는 가짓수
• ...

 

3. 첫번째 동전에서부터 1~k원을 만드는 가짓수를 각각 만들어나간다

• dp 테이블에 누적시켜 계산한다
• 예시) 1, 2원짜리로 10원을 만들려고 하면
  • 1원으로 가능한 모든 액수 가짓수는 한가지뿐이다
  • 2원까지 고려하면,
  • dp[2] = dp[2] + dp[2-2] = 1 + 1 =2
  • dp[4] = dp[4] + dp[4-2] = 1 + 2 =3
  • dp[6] = dp[6] + dp[6-2] = 1 + 3 =4
  • dp[8] = dp[8] + dp[8-2] = 1 + 4 =5
  • dp[10] = dp[10] + dp[10-2] = 1 + 5 =6

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int k = pint(st.nextToken());
		int[] coin = new int[n];
		int[] dp = new int [k+1];
		dp[0]=1;
		
		for (int i = 0; i < n; i++) {
			coin[i] = pint(br.readLine());
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = coin[i]; j < k+1; j++) {
				dp[j] += dp[j-coin[i]];
			}
		}
		System.out.println(dp[k]);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면