[DP] 이코테 - 호율적인 화폐구성

-자바

package dp;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class MakingCash1 {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int n;
	private static int m;
	private static int[] arr;	//화폐의 가치를 담을 배열
	private static int[] 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() );
		m = Integer.parseInt( st.nextToken() );
		
		arr = new int[n];
		dp = new int[10001];
		for( int i=0; i<=m; i++ ) dp[i] = 10001;
		
		for( int i=0; i<n; i++ ) arr[i] = Integer.parseInt( br.readLine() );
		
		dp[0] = 0;
		for( int i=0; i<n; i++ ) {
			for( int j=arr[i]; j<=m; j++ ) {
				dp[j] = Math.min( dp[j], dp[j-arr[i]]+1 );
			}
		}
		
		if( dp[m] == 10001 ) System.out.println( "-1" );
		else System.out.println( dp[m] );
		
	}
}

 

 

-파이썬

n, m = map( int, input().split() )
arr = []

dp = [10001] * (m+1)

for i in range(0, n):
    arr.append( int(input()) )

dp[0] = 0

for i in range(n):
    for j in range( arr[i], m+1 ):
        dp[j] = min( dp[j], dp[j-arr[i]]+1 )

if dp[m] == 10001:
    print( "-1" )
else:
    print( dp[m] )