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

문제 링크: 22115번 창영이와 커피

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

 

처음의 접근

먼저 2차원 DP로 접근하여, 카페인을 K만큼 섭취할 수 있는지부터 확인하고, 별도의 테이블을 통해서 최소 커피 개수를 구해주었다.

 

1차 개선

생각해보면, 카페인을 K만큼 섭취할 수 있는지의 가능 여부와 최소 커피 개수를 따로 구할 필요가 없다. 최소 커피 개수를 구하는 과정 자체가 가능 여부를 구하는 과정을 포함하기 때문이다. [0, i]의 커피를 고려한다고 할 때, i를 증가시켜나가면서 i번째 커피를 포함시키지 않을 때(dp[j])와 i번째 커피를 포함시킬 때(dp[j - a[i]] + 1) 중 최소 커피 개수를 이용한다.

 

2차 개선

1차원 DP 배열을 통해서도 문제를 해결할 수 있다. 이 문제에서 DP 배열을 채우는 과정은 다음과 같다.

 

for (int i = 0; i < n; i++) { // i번째 커피까지 고려
	for (int j = k; j >= a[i]; j--) { // 카페인을 k만큼 섭취
        dp[j] = min(dp[j], dp[j - a[i]] + 1) // 최소 커피 개수
    }
}

 

여기서, 2차원 DP 배열을 이용할 때와 달리, 왜 j를 '감소'시켜나가면서 배열을 갱신하는지가 헷갈리는 부분이다. dp[j - a[i]]에서 알 수 있듯, DP 배열의 앞쪽의 원소를 이용하기 때문이다(2차원일 때에는 j를 증가시키든 감소시키든 상관없다. 또한 1차원일 때에도 중복해서 사용할 수 있는 경우, j를 증가시켜야 한다고 하는데 이 부분은 생각해보아야 할 듯하다).

 

예를 들어서 설명해보자면... 문제의 조건과 DP 배열의 상태가 다음과 같다고 하자.

 

coffee[0] = 2, coffee[1] = 3, coffee[2] = 1(아직 고려되지 않음)

i = 1일 때(coffee[0, 1]을 고려했을 때)

k	0	1	2	3
DP[k]	INF	INF	1	1

 

여기서 i를 2로 증가시켜, coffee[2](카페인 함량이 1)를 고려 대상에 포함시킨다고 하자.

 

DP[3]을 갱신하려고 하면,

→ DP[2]를 고려해야 한다.

그런데 이 DP[2]는, coffee[2]를 고려하지 않았을 때, 즉 2차원 DP라면 DP[1][2]을 의미한다.

 

DP[2]를 갱신하려고 하면,

→ DP[1]을 고려해야 한다.

이 DP[1]도 마찬가지로, 2차원 DP라면 DP[1][1]을 의미한다.

 

그런데 이러한 상황에서 DP[2]를 DP[3]보다 먼저 갱신해버리면, DP[3]을 갱신하고자 할 때 DP[2]는 더이상 DP[1][2]가 아니라 DP[2][2]이다. 따라서, 필요한 값을 잃어버리게 되므로 뒤에서부터 갱신해주는 것이다.