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));
}
}
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 17404번- RGB거리2 (0) | 2022.11.09 |
---|---|
[JAVA] 알고리즘 : 동적 계획법- 최대 점수 구하기(냅색 알고리즘) (0) | 2022.11.09 |
[JAVA] 백준 9465번- 스티커 (0) | 2022.11.08 |
[JAVA] 백준 11054번- 가장 긴 바이토닉 부분 수열 (0) | 2022.11.07 |
[JAVA] 백준 11722번- 가장 긴 감소하는 부분 수열 (0) | 2022.11.07 |