ALGORITHM
[JAVA] 알고리즘 : 동적 계획법- 동전교환(냅색 알고리즘)
연듀
2022. 11. 9. 10:41
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int n, m;
static int[] dp;
public int solution(int[] coin){
Arrays.fill(dp, Integer.MAX_VALUE); // 큰 값으로 초기화
dp[0] = 0;
for(int i=0; i<n; i++){
for(int j=coin[i]; j<=m; j++){ // 동전의 금액부터 거슬러줄 금액까지 증가
dp[j] = Math.min(dp[j], dp[j-coin[i]]+1); // 더 큰 값의 동전으로 대체 할 수 있는지 비교
}
}
return dp[m];
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt(); // 동전의 개수
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = kb.nextInt();
}
m = kb.nextInt(); // 거슬러줄 금액
dp = new int[m+1]; // dp[i] = 거슬러줄 금액 i를 만드는데 드는 최소 동전 개수
System.out.println(T.solution(arr));
}
}
반응형