백준 12865번 : 평범한 배낭

문제 접근

---

처음에는 무게 기준 내림차순으로 정렬해서 탐욕법으로 풀 수 있을거라고 생각했는데 예외가 있어서 안 됐다. 알고리즘 분류를 확인해보니까 

 

1. 큰 배열은 함수 안에서 호출하면 segmentation fault 난다.

 

문제 코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int cache[101][100001];

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int W[101], V[101];
	int N, K;
	
	fill(&cache[0][0], &cache[100][100000], 0);
	
	cin>>N>>K;
	
	for(int i=1; i<=N; ++i)
		cin>>W[i]>>V[i];
	
	for(int i=1; i<=N; ++i)
	{
		for(int j=1; j<=K; ++j)
		{
			if(W[i]<=j)
				cache[i][j] = max(cache[i-1][j], cache[i-1][j-W[i]] + V[i]);
			else
				cache[i][j] = cache[i-1][j];
		}
	}
	
	cout<<cache[N][K]<<'\n';
}