Yong's Tech Story

문제 풀이 (JAVA)

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

public class Main {

	public static void main(String[] args) throws IOException {
		// 동전 교환(냅색 알고리즘)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int[] dy = new int[M + 1];

		Arrays.fill(dy, Integer.MAX_VALUE); // 최소를 구할시 Dynamic 배열 최대값으로 초기화
		dy[0] = 0; // 첫번째 값은 0 (최소값)
		for (int i = 0; i < N; i++) {
			for (int j = arr[i]; j <= M; j++) {
				dy[j] = Math.min(dy[j], dy[j - arr[i]] + 1); // (이전 최소값 + 1)이 현재 값보다 작다면 교환
			}
		}
		System.out.println(dy[M]);
	}
}

정리

1. 해당 동전 문제의 첫번째 포인트는 각 숫자마다 최소 배열을 가지는 dy 배열을 선언하는 것이다.

2. 최소 값을 가져야 하기 때문에 Arrays.fill 함수를 사용하여 dy 배열을 MAX 값으로 초기화해준다.(단, dy[0]은 비교를 위해 0으로 초기화한다.

3. 문제를 풀기 위해서는 (이전 최솟값 +1) 에서 1은 현재 동전을 추가했을때의 경우로, (이전 최솟값 +1)이 현재 값보다 작다면 최솟값을 가지는 경우의 수 이기 때문에 더 작은 값으로 교체해주어야 한다. 이 문제의 핵심 포인트이다.