백준_동전2_2294

//알고리즘

1. dp

 -> dp 테이블을 k+1 크기로 만듦

 -> dp 테이블을 아주 큰 수로 초기화

 -> k수 마다 동전으로 만들 수 있는지 없는지를 판단함

    - k가 동전보다 클 때, dp[ k - 동전 ] 값이 max인지를 판단하여 아니라면 1+ dp[ k - 동전 ]

 -> 만들 수 있다면 최소값으로 갱신

 

 

 

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

public class 동전2_2294 {
	static int n, k, coin[], dp[];

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

		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		coin = new int[n];
		dp = new int[k + 1];

		for (int i = 0; i < n; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}

		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;

		for (int j = 1; j <= k; j++) {
			for (int i = 0; i < n; i++) {
				if (j >= coin[i]) {
					if (dp[j - coin[i]] == Integer.MAX_VALUE) continue;
					int cal = 1 + dp[j - coin[i]];
					if (cal < dp[j]) dp[j] = cal;
				}

			}
		}

		System.out.println(dp[k] == Integer.MAX_VALUE ? -1 : dp[k]);

	}

}

 

※ dp 는 항상 느끼지만 설명하기가 어렵다...

 

	0	1	2	3	4	5	6	7	8	9	10
3	0	max	max	1	max	max	2	max	max	3	max
4	0	max	max	1	1	max	2	2	2	3	max