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.코드

4.배운점

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

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

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