[백준] 22115 창영이와 커피 - Java

 

 

문제 출저 

https://www.acmicpc.net/problem/22115

22115번: 창영이와 커피

 

 

 

문제 풀이

목표 카페인을 달성하기 위해 최소한의 커피 갯수를 구하는 문제입니다. 

 

배낭 알고리즘을 적용하여 문제를 풀었습니다. 

역순으로 탐색을 진행하여 중복을 제거하며 문제를 풀었습니다. 

 

 

 

소스코드

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

/*
창영이와 커피
https://www.acmicpc.net/problem/22115

10% 오답
dfs에서 for문으로 변경
배낭 알고리즘 적용
역순으로 확인해야 중복하지 않는다.

 */

public class Main {

    static int n;
    static int k;
    static int[] coffees;
    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        coffees = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            coffees[i] = Integer.parseInt(st.nextToken());
        }

        dp = new int[k+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;


        for (int i = 0; i < n; i++) {

            int coffee = coffees[i];
            // 중복 방지를 위해 역순으로 확인
            for (int j = k; j >= 0; j--) {
                if (j - coffee >= 0 && dp[j-coffee] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j-coffee] + 1);
            }
        }

        System.out.println(dp[k] == Integer.MAX_VALUE ? -1 : dp[k]);

    }



}