05. 동전교환

 

설명

동전 거슬러주기

 

 

예시

3
1 2 5
15

 

3

 

 

 

 

풀이

1. arrays.fill(dis,Integer.MAX_VALUE);

dis[0]=0;

 

 

2. for(int i=0; i<n ;i++) {
for(int j=arr[i]; j<=m; j++) {
dis[j]=Math.min(dis[j], dis[(j-arr[i])]+1);
}
}

import java.util.*;


class Main {
	
	public static void main(String[] args){
		
		Scanner sc= new Scanner(System.in);
		
		int n= sc.nextInt();
		int []arr= new int[n];
		
		for(int i=0; i<arr.length ;i++) {
			arr[i]=sc.nextInt();
		}
		
		int m = sc.nextInt();
		int [] dis= new int[m+1];
		Arrays.fill(dis, Integer.MAX_VALUE);
		dis[0]=0;
		
		for(int i=0; i<n ;i++) {
			for(int j=arr[i]; j<=m; j++) {
				dis[j]=Math.min(dis[j], dis[(j-arr[i])]+1);
			}
		}
		
		System.out.println(dis[m]);

	}

	
}