[BeakJoon 1480] 보석 모으기

안녕하세요. 이번 포스팅에서는 백준 1480 보석 모으기 문제를 풀어보도록 하겠습니다. 

해당 문제는 

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

1480번: 보석 모으기

 

위 링크에서 확인하실 수 있습니다.

 

처음 이 문제를 보았을 때 각 가방의 한도가 같기 때문에 투 포인터 형식으로 접근을 하였는데, 해당 방식이 최적해를 구하지 못합니다. 따라서 이 문제는 Dynamic Programming으로 모든 status에 대한 검사를 해야 합니다.

 

가방의 관점에서 현재 남은 용량으로 보석을 어떤 것을 담았을 때 최적 값인지를 고민하시면 됩니다.

 

이렇게 되면, 현재 검사하고 있는 가방 인덱스와 가방 용량으로 얼마나 담을 수 있는지, subproblem의 최적해를 찾은 뒤, 가방 인덱스를 하나씩 넘기면서 현재의 값과 비교하며, 최종적인 답을 도출하시면 됩니다.

 

보석의 개수가 적기 때문에 bitmasking을 활용해서 어떤 보석을 담았고, 담지 않았는지 체크하실 수 있습니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, c;
vector<int> v;
int dp[24][1<<14][24];
int go(int bagIdx, int path, int cap) {
	if(bagIdx == m) return 0;
	int& ret = dp[bagIdx][path][cap];
	if(ret) return ret;	

	// 현재 status에서 최적해를 찾는다!
	for(int i = 0; i < n; i++) {
		if((((1<<i)&path) == 0) && cap >= v[i]) {
			ret = max(ret, go(bagIdx, path|(1<<i), cap-v[i])+1);
		}
	}
	
    	// 가방 인덱스를 넘겨서 다음 가방의 상태의 최적해와 비교한다!
	ret = max(ret, go(bagIdx+1, path, c));
	return ret;
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> c;
	
	for(int i = 0; i < n; i++) {
		int a; cin >> a; v.push_back(a);
	}
	cout << go(0, 0, c) << "\n";
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.