[JAVA] 백준 알고리즘 2294 : 동전 2 (DP)

문제

소스

import java.util.Scanner;

public class Main {

	static int coin[], sum[];
	static int N, K;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // N가지 종류의 동전
		K = sc.nextInt(); // 동전의 합

		coin = new int[N+1];
		sum = new int[K+1];
	
		for(int i=0; i<N; i++) {
			coin[i] = sc.nextInt();
		}

		dp();
	}
	
	public static void dp() {
		
		for (int i=0; i<N; i++) {
			
			int cur = coin[i]; // 현재 동전
			
			for (int j=cur; j<=K; j++) {
				
				if (j == cur) {
					sum[j] = 1;
					continue;
				}
				
				// 동전 조합
				if ((sum[j] == 0 || sum[j] >= sum[j-cur]+1) // 체크되지 않은 조합이거나 해당 조합이 최소값일 경우
						&& sum[j-cur] != 0) // 동전의 조합으로 더해져서 나온 값이 존재할 경우
				{
					sum[j] = sum[j-cur]+1;
				}
			}
		}		
		
		System.out.println(sum[K] == 0 ? -1 : sum[K]);
	}
}

출처

https://www.acmicpc.net/problem/2294