[Knapsack] 냅색은 웬만해선 바텀업으로 짜자

knapsack dp를 알고 있는가?

아래 문제는 굉장히 유명해서 모두들 알고 있을 것이다. (0-1 knapsack의 Standard)

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

12865번: 평범한 배낭

위 문제는 N 범위가 워낙 작아서

탑다운이든 바텀업이든 다 뚫린다.

이 문제만 보면 어떻게 풀어도 상관없겠다는 생각이 들 수 있다.

---

탑다운? 써도 상관없을 것 같은데?

나도 웬만한 dp는 탑다운으로 푸는 것을 선호한다.

그러나 knapsack은 웬만해선 바텀업 풀이가 훨씬 좋다.

메모리가 절약되는 건 물론이고, 제일 중요한건 시간복잡도 자체가 달라진다!

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

3067번: Coins

이 문제를 한번 풀어보자.

재귀로 0ms가 나왔다면 풀이를 댓글로 알려주길 바랍니다.

 

N가지 종류의 동전 a[1]원, a[2]원, ..., a[N]원짜리 동전들로 M원을 만드는 경우의 수를 구하는 방법을 생각해보자.

참고로 12865번과 다르게 같은 동전을 여러개 써도 상관없다.

따라서 현재 남은 금액이 k원이고, i번째 동전을 탐색하고 있을 때, for문으로 0 ~ k/a[i] 까지 돌려주면 되겠다.

 

탑다운 코드 (시간 초과)

#include <bits/stdc++.h>
using namespace std;
int t,n,m,a[22],d[22][10011];
int dp(int cur,int sum){
	if(cur>=n)return !sum?1:0;
	int&ret=d[cur][sum];
	if(ret!=-1)return ret;
	ret=0;
	for(int i=0;i<=sum/a[cur];i++){
		ret+=dp(cur+1,sum-a[cur]*i);
	}
	return ret;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>t;
    while(t--){
    	cin>>n;
    	for(int i=0;i<n;i++)cin>>a[i];
    	cin>>m;
    	memset(d,-1,sizeof(d));
    	cout<<dp(0,m)<<"\n";
    }
}

그러나 탑다운으로 위와 같이 짜서 제출하면 TLE를 받게 된다.

시간복잡도가 O(N*M*(M/N)*T)이므로 약 O(20*10000*500*T)=O(1e8 * T)가 되기 때문이다.

 

탑다운 코드2 (760ms)

#include <bits/stdc++.h>
using namespace std;
int t,n,m,a[22],d[22][10011];
int dp(int cur,int sum){
	if(cur>=n)return !sum?1:0;
	if(!sum) return 1;
	int&ret=d[cur][sum];
	if(ret!=-1)return ret;
	ret=0;
	for(;sum>=0;sum-=a[cur]){
		ret+=dp(cur+1,sum);
	}
	return ret;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>t;
    while(t--){
    	cin>>n;
    	for(int i=0;i<n;i++)cin>>a[i];
    	cin>>m;
    	memset(d,-1,sizeof(d));
    	cout<<dp(0,m)<<"\n";
    }
}

거의 비슷한 코드인데 약간의 조작만으로 겨우겨우 통과가 됐다.

시간복잡도 상으로 거의 큰 차이는 없을 듯 하지만, 이건 통과가 되고 위에껀 통과가 안되는 게 신기할 뿐...

 

자, 그럼 바텀업 코드도 보자.

 

바텀업 코드 (0ms)

#include <bits/stdc++.h>
using namespace std;
int t,n,m,a[22],d[10011];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>t;
    while(t--){
    	memset(d,0,sizeof(d));
    	cin>>n;
    	for(int i=0;i<n;i++)cin>>a[i];
    	cin>>m;
    	d[0]=1;
    	for(int i=0;i<n;i++){
    		for(int j=a[i];j<=m;j++){
    			d[j]+=d[j-a[i]];
    		}
    	}
    	cout<<d[m]<<"\n";
    }
}

dp table 자체가 일차원 배열인데다가,

시간복잡도도 O(N*M*T)로 훨씬 단축된 것을 볼 수 있다.

 

재귀로는 index, sum이 변할 경우, 둘 다 인자로 줘야 하기 때문에 이차원배열로 밖에 접근하지 못하기 때문에 시간복잡도 단축이 불가능하다. 

---

이 쯤 되면 평범한배낭 문제를 풀 때는 느끼지 못했던 시간복잡도 단축을, 이 문제를 통해 뼈저리게 느꼈을 것이라 본다.

바텀업에 약하더라도, knapsack은 바텀업으로 짜는 것을 추천한다.

 

연습문제로 연습하고 싶다면 아래 포스팅 참고!

https://kth990303.tistory.com/216

[Knapsack DP] 냅색은 바텀업으로 - 연습문제 유형익히기