BaekJoon 12865번: 평범한 배낭

풀이법

1) DP를 이용하지 않으면 시간 초과가 일어날 수 있기에 DP를 이용해야 한다.

2) 유명한 0-1 Knapsack문제로 알고리즘 수업을 들은 학생들은 점화식을 생각해 내기 쉬울 것이다.

3) 점화식을 어떻게 세울지를 직접 고민하는 것이 추후 DP 문제를 풀 때 더 도움이 될 듯하여 자세한 풀이는 적지 않았다. 밑의 소스 코드에는 답이 있으므로 꼭 깊이 있게 생각하고 읽어주길 바란다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector<pair<int, int>>arr;
bool visited[101];
long long maxNum = -1;
int ans[100001];
void dfs(int weight, int value,int index)
{
	if (weight > k)
	{
		return;
	}
	if (weight <= k && maxNum < value)
	{
		maxNum = value;
	}
	for (int i = index; i < n; i++)
	{
		if (visited[i])
		{
			continue;
		}
		visited[i] = true;
		//weight += arr[i].first;// 이방식 이용하면 최적해 13 출력
		//value += arr[i].second;
		dfs(weight+arr[i].first, value+arr[i].second,i); 
		// 4 7 6 13 4 8 1 0 3 6 넣을시 최적해 14 출력
		visited[i] = false;
	}
}
void dp()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = k; j >= 1; j--)
		{
			if (arr[i].first <= j)
			{
				ans[j] = max(ans[j], ans[j - arr[i].first] + arr[i].second);
			}
		}
	}
	cout << ans[k];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		int w, v;
		cin >> w >> v;
		arr.push_back({ w,v });
	}
	dfs(0, 0,0);
	cout << "\n";
	cout << "dfs 풀이" << "\n";
	cout << maxNum<<"\n";
	cout << "dp 풀이" << "\n";
	dp();

}

한계점 및 개선사항 (+주의사항)

BFS를 사용하면 무조건 시간 초과가 난다. 생각 없이 BFS로 대충 풀어야지 하고 풀었다가 호되게 당했다. 시간 복잡도를 줄이기 위한 DP만이 답인 문제이다. 문제를 풀기 전에 조금 더 깊이 있게 생각하고 문제에 접근해야겠다.

(BaekJoon 통과가 목적이 아닌 BFS를 연습하기 위해서 이 문제를 푸는 분들을 위해 BFS Source Code 또한 같이 첨부 하였다.)

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest