[백준온라인] 22115번 창영이와 커피

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

22115번: 창영이와 커피

문제 요약 : 원하는 양의 카페인을 위한 커피 최소 개수 출력

입력	출력
1 ≤ N(커피) ≤ 100 0 ≤ K(카페인) ≤ 100000 1 ≤ C(카페인 함유량) ≤ 1000	K만큼 카페인을 섭취하기 위한 커피의 최소 개수

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_22115.java

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
30871682	cbkpar	22115	맞았습니다!!	14596KB	168ms	Java 11	747B

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));
		int n,k,c,i;
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		int[] dp = new int[k+1];
		st = new StringTokenizer(br.readLine());
		Arrays.fill(dp, 1000000000);
		dp[0] = 0;
		while(n-->0) {
			c = Integer.parseInt(st.nextToken());
			for(i=k;i>=c;i--) dp[i] = Math.min(dp[i], dp[i-c]+1);
		}
		System.out.println(dp[k]>100?"-1":dp[k]);
	}
}

K+1칸의 배열을 만들고 각 칸을 0~K만큼 의 카페인을 위해 섭취한 커피 개수라한다.

이때 모든 칸을 -1로 초기화 한후 필요한 카페인이 0일땐 커피를 마시지 않아도 되므로 0으로 초기화한다.

그 후 커피를 하나씩 확인하며 커피의 카페인 함유량을 C라고 한다면

K부터 C까지 필요한 커피의 개수를 수정해준다.

 

예제 ) 

커피의 수 : 4

필요한 카페인 : 5

카페인 함유량 : 1 1 3 2