백준_2293 동전1(자바) / DP

시간 & 메모리 제한

문제

입력 & 출력

DP를 이용한 문제풀이

package com.Back;

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

public class Back_2293 {

	public static void main(String[] args) throws Exception {
		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());
		
		//1~10까지
		int [] dp = new int[k+1];
		dp[0] = 1;
		int temp;
		for (int i = 0; i < n; i++) {
			temp = Integer.parseInt(br.readLine());
			for (int j = 1; j < k+1; j++) {
				if(j>=temp) dp[j] += dp[j-temp];
			}
		}
			System.out.println(dp[k]);
	}
}

- DP를 이용해서 문제를 풀면 쉽게 풀 수 있습니다.

 

- 이 문제의 경우 점화식을 만드는 방법이 중요하다.

 

예제의 경우를 통해서 힌트를 얻으면