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

• 백준 문제 URL

---

문제 요약

서로 다른 커피가 N개 있고, 각 커피는 카페인 양이 정해져 있다
몇 개의 커피를 골라 카페인 합을 정확히 K로 만들 때, 마셔야 하는 커피 개수의 최솟값을 구하는 문제다
만약 정확히 K를 만들 수 없다면 -1을 출력한다

---

핵심 아이디어

각 커피는 한 번만 선택 가능하므로, 전형적인 0/1 배낭(Subset) DP 형태로 바꿀 수 있다
dp[j]를 “카페인 합을 정확히 j로 만들 때 필요한 최소 커피 개수”로 두고, 가능한 경우를 누적 갱신한다
같은 커피를 중복 사용하지 않기 위해 j를 K부터 내려오며(역순) 업데이트하는 것이 핵심이다.

---

DP 정의 & 점화식

dp 정의

• dp[j] = 카페인 합을 정확히 j로 만들 때 필요한 최소 커피 개수 (불가능하면 INF)

---

초기값

• 아무 커피도 안 마시면 합이 0이므로
  dp[0] = 0
• 나머지는 불가능 상태로 시작
  dp[1..K] = INF

---

점화식

현재 커피의 카페인을 c라고 하면:

• 커피를 안 마시는 경우: dp[j] 유지
• 커피를 마시는 경우: 직전 합이 j - c여야 하므로 dp[j - c] + 1

따라서

dp[j] = min(dp[j], dp[j - c] + 1)

또한 한 커피를 한 번만 쓰기 위해 j는 큰 값부터 내려오며 갱신한다.

---

최종 답

• dp[K]가 INF 이상이면 만들 수 없는 경우이므로 -1
• 아니면 dp[K] 출력

---

전체 코드(제출용)

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 K = Integer.parseInt(st.nextToken()); // 목표 카페인 합

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

        int INF = 100 * 1000;

        int[] dp = new int[K + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            int caffein = caffeineArr[i];
            for (int j = K; j >= caffein; j--) {
                dp[j] = Math.min(dp[j], dp[j - caffein] + 1);
            }
        }

        System.out.println(dp[K] >= INF ? -1 : dp[K]);
    }
}