22115 창영이와 커피 [DP]

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

22115번: 창영이와 커피

1.접근

백트래킹으로 생각하고 풀었다가 시간초과를 맞았다. k가 커질 수록 시간이 급격히 늘어나는 코드였다.

얻어야하는 카페인양과 커피들의 카페인양을 보고 냅색문제처럼 최적 부분 구조로 나누어 풀 수 있다는걸 알았다.

 

2.풀이

각 커피에 카페인이 1, 2, 3, 4, 5 가 들어있고 마셔야하는 카페인이 15라고 가정해보자.

만약 5가 커피의 최소 개수를 위해 꼭 마셔야하는 커피라면 15에서 5를 뺀 10의 카페인을 1,2,3,4커피를 가지고 마시는 경우 +1이 최소 개수의 커피를 마시는 케이스일 것이다. 즉 다이나믹 프로그래밍의 최적부분구조를 만족한다.

따라서 2차원 배열을 생성해서 DP[카페인][커피]를 생성한다.

커피를 마시는 순서는 상관없이 Bottom UP 방식으로 쌓아간다.

현재 인덱스의 커피값을 뺀 부분 +1과 안마신다는 가정으로 옆에서 가져오는 값을 비교한다.

DP[카페인][커피인덱스]=min(DP[카페인-커피인덱스의 카페인값][커피인덱스-1]+1, DP[카페인][커피인덱스-1])

그 후 기저 사례를 체크해주면 된다.

 

3.코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Arrays;
	import java.util.Collections;
	public class 창영이와커피_22115 {
	static int n,k,ans;
	static int[][] arr;
	static int cant=1001;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String[] s = br.readLine().split(" ");
	n=Integer.parseInt(s[0]);
	k=Integer.parseInt(s[1]);
	String[] ss=br.readLine().split(" ");
	int [] coffee=new int[ss.length];
	for (int i = 0; i < ss.length; i++) {
	coffee[i]=Integer.parseInt(ss[i]);
	}
	arr=new int[k+1][n+1];
	for (int i = 0; i < n+1; i++) {
	arr[0][i]=0;
	}
	for (int i = 1; i <k+1; i++) {
	for (int j = 0; j <n+1; j++) {
	arr[i][j]=cant;
	}
	}
	for (int i = 1; i <k+1; i++) {
	for (int j = 1; j <n+1; j++) {
	if (i-coffee[j-1]<0) arr[i][j]=arr[i][j-1];
	else if (!(arr[i - coffee[j-1]][j - 1] == cant && arr[i][j - 1] == cant)) {
	arr[i][j]=Math.min(arr[i][j-1],arr[i-coffee[j-1]][j-1]+1);
	}
	}
	}
	ans=arr[k][n];
	if (ans == cant) {
	System.out.println(-1);
	} else {
	System.out.println(ans);
	}
	}
	}

view raw 창영이와 커피.java hosted with ❤ by GitHub

4.배운점

오랜만에 만나보는 문제라 다이나믹 프로그래밍적 사고를 하는데 오래걸렸다.

정렬도 생각났지만 순서가 상관없이 쌓아 올라간다는게 중요했다.

DP 에서 기저 사례를 더 꼼꼼히 체크하자.