BOJ 2728 오늘은 마가리타 한 잔?

문제 링크입니다.

관찰

가게마다 마가리타가 하나씩 준비되어 있을 때, 주어진 예산을 더 이상 살 수 있는 마가리타가 없을 때까지 써서 살 수 있는 마가리타의 조합의 수를 구해야 합니다.

더 이상 살 수 있는 마가리타가 없다는 것은, 마가리타를 모두 산 뒤 남은 돈이 사지 않은 가장 싼 마가리타보다 작다는 의미가 됩니다. 여기에서 착안해, 마가리타를 사는 방법을 가장 싼 마가리타를 사는 경우와 그렇지 않은 경우로 나누어 생각합시다.

가장 싼 마가리타를 사지 않는다면

이 경우, 나머지 마가리타를 사서 가장 싼 마가리타의 가격보다 적은 돈을 남겨야 합니다. 이는 냅색 DP로 해결할 수 있습니다.

• D[j] : 가장 싼 마가리타를 제외하고, 정확히 j의 예산을 사용해서 마가리타를 구매하는 방법의 수

총 예산이 K, 가장 싼 마가리타의 가격을 V라고 하면, 가장 싼 마가리타를 사지 않는 방법의 수는 D[K - V+1] 부터 D[K] 까지의 합입니다.

가장 싼 마가리타를 산다면

이 경우, 예산에서 가장 싼 마가리타의 가격을 빼고 가장 싼 마가리타를 버립니다. 그러면 남은 예산으로 남은 마가리타를 사는, 그러니까 직전과 값만 다르고 똑같은 상황이 됩니다.

이를 일반화하면 마가리타를 가격 순으로 정렬했을 때, 앞에서부터 순서대로 t개의 마가리타를 모두 사고, t+1 번째 마가리타는 사지 않는 경우를 모두 더해 답을 구할 수 있습니다.

어느 마가리타도 살 수 없는 경우와 모든 마가리타를 살 수 있는 경우를 주의해서 처리하면 총 시간 복잡도 테스트 케이스 당 $\mathcal{O}(N^2K)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans, a[33], d[1234];
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int T; cin >> T; while(T--){
		ans = 0;
		int n, k; cin >> n >> k;
		ll s = 0;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			s += a[i];
		}
		if(s <= k){
			cout << "1\n";
			continue;
		}
		sort(a+1, a+n+1);
		if(a[1] > k){
			cout << "0\n";
			continue;
		}
		for(int ex = 1; ex <= n; ex++){
			memset(d, 0, sizeof(d));
			d[0] = 1;
			for(int i = ex+1; i <= n; i++){
				for(int j = k; j >= a[i]; j--){
					d[j] += d[j-a[i]];
				}
			}
			for(int j = k; j > max(-1LL, k-a[ex]); j--) ans += d[j];
			k -= a[ex];
			if(k < 0) break;
		}
		cout << ans << '\n';
	}
}