[알고리즘] 백준 1480 보석 모으기

📖문제

1480 보석 모으기

💡구상

1. 보석을 무게 상관없이 최대한 많이 담으면 되니까 보석을 무게 순서대로 정렬한 후 계속 담아나가면 되지 않을까??

• 예제 입력2) 처럼 1 3 5 2 4 입력이 들어왔을때, {1,4},{3,2} 이런식으로 담아야 하지만 위 방식은 {1,2} {3} 총 3개를 담으므로 실패

2. 그럼 모든 수를 고려해서 완전탐색을 진행해보자.

• 완전탐색을 진행할 경우 경우의수는 최대 20! 이므로 실패

3. 그렇다면 최후의 DP

• 아래 코드와 함께 살펴보자

🔍코드

#include<bits/stdc++.h> 
using namespace std;
int n,m,c;
int a[21];
int dp[21][1<<14][21];
int go(int bag, int jewl, int capacity){
	if(bag == m) return 0;
	int &ret = dp[bag][jewl][capacity];
	if(ret) return ret;
	
	// 담지 않을때
	ret = max(ret, go(bag+1,jewl,c));
	// 담을때 
	for(int i=0; i<n; i++){
		bool isInBag = (1<<i) & jewl;
		bool canInBag = (capacity - a[i]) >= 0;
		if(!isInBag && canInBag) ret = max(ret,go(bag,jewl | (1<<i), capacity-a[i])+1);
	}
	return ret;
}
int main(){
	cin>>n>>m>>c;
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	cout<<go(0,0,c);
	
}

우선 DP 배열에 어떠한 상태값이 필요할지 생각해보자.
우선 제한이 있는 값인 가방, 용량은 필요할 것이다. 그리고 비트연산자를 활용하여 탐색을 진행하며 i번째 보석을 이미 담았는지 확인하는 수 jewl (1<<14) 가 필요하다.

int dp[21][1<<14][21];

이제 탐색을 진행하며 우리는 2가지의 경우의 수를 고려해주면 된다.

• 현재 가방에 담지 않는 경우
• 현재 가방에 담는 경우

현재 가방에 담지 않는 경우

ret = max(ret, go(bag+1,jewl,c));

가방에 담지 않는다면, 다음 가방으로 넘어가고, capacity(현재 담을 수 있는 용량)을 c(최대 용량)으로 갱신해준다.

현재 가방에 담는 경우

for(int i=0; i<n; i++){
	bool isInBag = (1<<i) & jewl;
	bool canInBag = (capacity - a[i]) >= 0;
	if(!isInBag && canInBag) ret = max(ret,go(bag,jewl | (1<<i), capacity-a[i])+1);
}

모든 보석을 탐색하며 2가지를 고려해주면 된다.

• 가방에 담긴 보석인지 아닌지
• 보석의 무게를 현재 가방에 담았을 수 있는지

bool isInBag = (1<<i) & jewl;

가방에 담긴 보석인지 아닌지를 체크하기 위해 비트연산자를 활용하여 isInBag 변수에 체크한다.

bool canInBag = (capacity - a[i]) >= 0;

가방에 담을 수 있는지를 체크하기 위해 canInBag 변수에 체크한다.

if(!isInBag && canInBag) ret = max(ret,go(bag,jewl | (1<<i), capacity-a[i])+1);

두 조건을 모두 만족한다면, jewl에 새로 담는 보석을 갱신해주고, 현재용량도 갱신해준다.

그렇게 계속 탐색해나가면 최댓값을 구할 수 있다!!