[2293] 동전 1

동적 프로그래밍 문제

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	// 첫줄에서 n과 k 입력 받기 위한 임시 String배열 line
		String[] line = br.readLine().split(" ");
		int n = Integer.parseInt(line[0]);
		int k = Integer.parseInt(line[1]);
        // 동전의 가치를 저장하기 위한 int배열 coin
		int[] coin = new int[n];
        // 동적프로그래밍을 사용하기위한 int배열 dp
		int[] dp = new int[k + 1];
		for (int i = 0; i < n; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}
        // 초기값 설정
		dp[0] = 1;
        // 동전의 수만큼
		for(int i=0; i<n; i++) {
        	// 1부터 k까지 coin[i]를 사용해서 만들 수 있는 가짓수 찾기
			for(int j=1; j<=k; j++) {
				if(j - coin[i] >= 0) {
					dp[j] = dp[j] + dp[j - coin[i]];
				}
			}
		}
		System.out.println(dp[k]);
	}
}

 

다른 사람의 아이디어를 참고해서 풀었다.

아직도 점화식 세우는데 익숙치않다.