[JAVA64] 2294. 동전2

2294. 동전2 (G5)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	80255	25017	17756	30.095 %

 

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

 

출력

 

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

---

summary

합 K 만들 때 사용되는 동전 최소개수 구하기

• 가진 동전으로 만들 수 없는 경우 -1 출력

 

strategy

다이나믹 프로그래밍 (DP) 활용

• N 개 동전 정보 저장 (dice)
• K 에 사용되는 동전 최소 개수 저장 (DP)
• DP[k] 마다 모든 coins[n] 을 사용한 개수를 계산 (DP[k - coin[n]] + 1) 
  • K = 20 에서 코인10을 사용하려면 K = 10 에서 +1 을 하면 됨

 

note

• 1 ≤ n ≤ 100
• 1 ≤ k ≤ 10,000
• 최대 10,000 X 100 = 10,000,000 이라서 시간 문제 X

 

import java.util.*;
import java.io.*;

public class Main {

    static int N, K;
    static int[] coins, DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer input = new StringTokenizer(br.readLine());
        N = Integer.parseInt(input.nextToken());
        K = Integer.parseInt(input.nextToken());

        coins = new int[N];
        DP = new int[K + 1];
        for(int n = 0; n < N; n++) {
            int coin = Integer.parseInt(br.readLine());

            coins[n] = coin;
        }

        for(int currentNum = 1; currentNum <= K; currentNum++) {
            
            int minUseDice = 100_000;
            for(int n = 0; n < N; n++) {
                if(currentNum < coins[n]) continue;

                int useCurrentDice = DP[currentNum - coins[n]] + 1;
                minUseDice = Math.min(useCurrentDice, minUseDice);
            }

            DP[currentNum] = minUseDice;
        }

        System.out.println(DP[K] == 100000 ? -1: DP[K]);

        br.close();
    }
}

문제	결과	메모리	시간	언어코드	길이
2294	맞았습니다!!	14332 KB	124 ms	Java 11 / 수정	1111 B

memo

• 동전 못 만드는 경우 -1 출력을 적어놓고 놓쳐서 틀림
• 이중 for 문에서 coin 정보를 바깥 for 문으로 하면 속도 더 향상됨

Arrays.fill(DP, 100000);

for(int n = 0; n < N; n++) {
	for(int k = coins[n]; k <= K; k++) {
		DP[k] = Math.min(DP[k - coins[n]] + 1, DP[K]);
	}
}