동전교환(Dynamic Programing)

 

동전 교환

 

 

 

 

 

코드

package dynamic;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 동전교환(냅색 알고리즘)
 * N 제한이 적으면 DFS로 풀이 가능하지만 N제한이 커지면 동적계획법으로 풀이하여야 함
 */
public class Dynamic4 {
    static int[] dy; // 최소 개수를 계속해서 기록

    static int solution(int[] coin, int totalMoney) {
        Arrays.fill(dy, Integer.MAX_VALUE);

        for (int i = 0; i < coin.length; i++) { // 동전의 개수 만큼
            dy[0] = 0;

            for (int j = coin[i]; j <= totalMoney; j++) {
                // 기존 값보다 작으면 바꿔준다
                dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1);
            }
        }
        return dy[totalMoney];
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] coin = new int[N]; // 동전 종류 배열

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            coin[i] = Integer.parseInt(st.nextToken());
        }

        int totalMoney = Integer.parseInt(br.readLine());

        dy = new int[totalMoney + 1];

        System.out.println(solution(coin, totalMoney));
        br.close();
    }
    
}