백준 : 2293 : 동전 1 (DP)

이번문제 역시 DP 문제중 하나이다.

 

매번 풀때마다 느끼는 거지만 DP문제는 어려운것 같다. 많이 풀어보도록 해야겠다.

 

구현하는것은 어렵지 않으나, 점화식 및 규칙을 찾는 부분이 어렵게 느껴진다.

 

이번문제는 비슷하게 접근은 했으나, 규칙을 찾지 못해 풀이를 찾은 후 이해한 뒤 풀어보았다.

 

풀이는 아래 사진을 참고하면된다. 

 

다음에 이와같이 DP문제가 나왔을때 이번 경험을 토대로 잘 풀 수 있었으면 좋겠다. 화이팅!!!

import java.util.*;

class Main{
	
	static int n, m;
	static int[] coin, dp;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		sc.nextLine(); //버퍼
		
		//초기화
		coin = new int[n];
		dp = new int[m+1];
		
		dp[0] =1; //주의******
		
		for(int i=0; i<n; i++) { //동전갯수만큼
			coin[i] = sc.nextInt();
		}
		
		for(int i =0; i<n; i++) { //찾아야하는 동전 크기만큼
			for(int j= coin[i]; j < m+1; j++) { //주의******
				dp[j] += dp[j - coin[i]];
			}
		}

		System.out.println(dp[m]);
	}
	
	
}