백준 2294. 동전 2

문제 링크

난이도	정답률(_%)
Silver 1	28.053%

설계

• 동전의 가짓수 N (<= 100)
• 원하는 가치 K (<= 10,000)
• 각 가치값에 필요한 동전의 개수를 계산해 더 적은 동전의 개수값을 저장한다.

시간 복잡도

• O(N * K)

공간 복잡도

• 가치 크기만큼의 int형 배열 K + 1
• 동전 가짓수 만큼의 int형 배열 N

풀이

• 0을 제외한 모든 가치의 초기값을 100001로 설정한다.

이는 문제에서 어떤 가치를 만들 수 있는 최대 동전의 개수로, 더 작은 동전의 개수를 계산하기 쉽도록 초기값으로 설정했다.

• 모든 동전에 대해 아래와 같은 과정을 반복한다.
  • 동전의 가치 ~ K (원하는 가치)까지 순회하면서 필요한 동전의 개수를 계산한다.

  여기서 처음이 아닌 동전의 가치번째부터 순회하는 이유는 동전의 가치보다 적은 가치는 그 동전으로 만들 수 없기 때문이다.

  • 각 가치에서 필요한 동전의 개수는 coinNumberOfValue 배열 현재 가치 - 동전의 가치 인덱스의 값 + 1이다.

  현재 동전의 가치만큼을 동전 1개로 채울 수 있으므로, 그 가치값만큼 동전의 개수를 없애고 동전 1개로 변경하는 과정이다.

  • 이 값과 기존에 있는 값을 비교해서 더 작은 값을 배열에 저장한다.
• 배열의 마지막 인덱스에 있는 값이 해당 가치에서 필요한 가장 적은 동전의 수이다.

예제로 본 풀이

동전 {1, 5, 12}, 원하는 가치 = 15

• 초기 설정

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	100001	100001	100001	100001	100001	100001	100001	100001	100001	100001	100001	100001	100001	100001	100001

• 가치가 1인 동전을 사용했을 때 필요한 동전 수 계산

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

• 가치가 5인 동전도 사용했을 때 필요한 동전 수 계산

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3

• 가치가 12인 동전도 사용했을 때 필요한 동전 수 계산

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

결과

메모리	실행 시간
13464KB	96ms

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] information = br.readLine().split(" ");
        int coinNumber = Integer.parseInt(information[0]);
        int price = Integer.parseInt(information[1]);
        int[] coins = new int[coinNumber];
        int[] coinNumberOfValue = new int[price + 1];

        for (int i = 0; i < coinNumber; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        Arrays.fill(coinNumberOfValue, 100001);
        coinNumberOfValue[0] = 0;

        for (int i = 0; i < coinNumber; i++) {
            for (int j = coins[i]; j <= price; j++) {
                coinNumberOfValue[j] = Math.min(coinNumberOfValue[j], coinNumberOfValue[j - coins[i]] + 1);
            }
        }

        bw.write(String.valueOf(coinNumberOfValue[price] == 100001 ? -1 : coinNumberOfValue[price]));

        bw.flush();
        bw.close();
    }
}