2294번 동전2, K원이 되도록 하는 동전의 개수 최소 구하기

[[2023-11-21-day39#2293 K원 동전 만드는 경우의 수 구하기]] 위 문제와 비슷해서 풀 수 있었다. 1시간 30분 걸림. 동전의 개수를 최소로 해야하므로 2293번 문제와 좀 달랐다. dp가 사용된다는 걸 보고 맞췄다ㅠ_ㅠ dp, dfs, bfs, 백트래킹 뭐 여기서 나오겠지 하고 생각했어야… dp[i] : i원을 만드는 동전 개수의 최소값 막막하다가 그냥 규칙 나열해보자 싶어서 나열했더니 1, 5, 12원이 각각 있으면 작은 것부터 그냥 하면 되더라. dp[value] = dp[value - coin] + dp[coin]; dp[coin] = 1 고정이니까 그냥 1로 씀.

  • 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  • 1 2 3 4 1 2 3 4 5 2 3 4 5 6 3
  • 12원 시작 *———————— 1 2 3 3
  • 1 먼저 돌리고 그다음 5돌리고 그 다음 12 돌리는 식으로 하면 최소값을 찾을 수 있다는 걸 깨닫고 코드 구현 시작.
import java.util.*;  
import java.io.*;  
  
public class BJ_2294 {  
  
    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 k = Integer.parseInt(st.nextToken());  
        int maxCoin = 100_000;  
        int[] coins = new int[maxCoin + 1];  
        int[] dp = new int[k+1];  
        Arrays.fill(dp, Integer.MAX_VALUE);  
        // dp[i] : i원의 가치를 만드는 동전의 최소 개수  
        dp[0] = 0;  
  
        while(n-- > 0) {  
            int coin = Integer.parseInt(br.readLine());  
            coins[coin] = coin;  
        }  
  
        for(int coin = 1; coin <= maxCoin; coin++) {  
            if(coins[coin] != 0) {  
                for (int value = coin; value <= k; value++) {  
                    if(dp[value - coin] != Integer.MAX_VALUE) {  
                        if(dp[value] > dp[value - coin] + 1) {  
                            dp[value] = dp[value - coin] + 1;  
                        }  
                    }  
  
                }  
            }  
        }  
        //System.out.println(Arrays.toString(dp));  
        if(dp[k] == Integer.MAX_VALUE) System.out.println(-1);  
        else System.out.println(dp[k]);  
    }  
}

Math.min 이란걸 이용해서 min 쓸 수 있당.

for(int i=1;i<=n;i++){
            for(int j=arr[i];j<=k;j++){
                dp[j]=Math.min(dp[j],dp[j-arr[i]]+1);
            }
        }

그리고 나처럼 이상하게 안하고… 이렇게 첫번째 포문 n번만 돌림. 중복으로 돌려도 상관없어서 그런가봐?

for (int i = 0; i < n; i++) {
			coin[i] = input.nextInt();
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = coin[i]; j <= k; j++) {
				dp[j] = Math.min(dp[j], 1 + dp[j - coin[i]]);
			}
		}