[백준] No.2629 - 양팔저울 (C++)

문제

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

2629번: 양팔저울

 

풀이

DP문제 중에서도 배낭 문제에 해당한다.

배낭 알고리즘은 특정 조건을 만족시키는 물건을 선택하는 조합을 구해낼 수 있다.

 

해당 문제에서 구슬의 무게를 알 수 있는 경우는 두 가지이다.

 

1. 구슬 VS 추가 평형을 이루는 경우

2. 구슬+추 VS 추가 평형을 이루는 경우

 

1번의 경우 단순히 현재 weight에서 idx 번째 추를 선택하거나 선택하지 않는 경우를 확인하는 점화식을 거치면 된다.

dp[weight][idx] = dp[weight - idx추의 무게][idx-1] || dp[weight][idx-1]

 

dp의 weight가 0인 경우만 모두 true 로 설정 해두고

idx는 모두 idx-1 번째 추로 넘어가 해당 추를 선택하거나 하지않는 경우의 탐색을 계속 진행한다.

 

최종적으로는 해당 무게(weight)를 추들의 조합을 만들수 있는 지의 여부는 dp[weight][weight_num]로 확인이 가능하다.

 

2번의 경우는 구슬의 무게 + 추의 무게 조합 = 추의 무게 조합 인 경우 해당 구슬의 무게를 확인이 가능하다.
따라서 모든 weight를 순회하면서, dp[weight][weight_num] 과 dp[weight+구슬의 무게][weight_num]가 모두 true인 경우를 확인하면 된다.

 

마지막으로 1,2번 중 한가지라도 true인 경우 Y를 출력해준다.

 

코드

	#include <iostream>
	#include<string.h>
	using namespace std;
	int main() {
	int weight_num, marble_num;
	int weight_list[31], marble_list[7];
	bool dp[40001][31];
	bool is_pos_marble[7];
	cin>>weight_num;
	for(int i=1; i<=weight_num ; ++i)
	cin>>weight_list[i];
	cin>>marble_num;
	for(int i=0; i<marble_num ; ++i)
	cin>>marble_list[i];
	memset(dp, false, sizeof(dp));
	for(int i=0; i<=weight_num ; ++i)
	dp[0][i] = true;
	for(int weight=1; weight<=40000 ;++weight )
	for(int idx=1; idx<=weight_num ; ++idx){
	if(weight - weight_list[idx] >=0)
	dp[weight][idx] |= dp[weight - weight_list[idx]][idx-1];
	dp[weight][idx] |= dp[weight][idx-1];
	}
	memset(is_pos_marble, false, sizeof(is_pos_marble));
	for(int i=0; i<marble_num ; ++i)
	for(int weight=1; weight<=40000-marble_list[i] ;++weight)
	if(dp[weight][weight_num] && dp[weight+marble_list[i]][weight_num])
	is_pos_marble[i] = true;
	for(int i=0; i<marble_num ; ++i){
	if(dp[marble_list[i]][weight_num] || is_pos_marble[i])
	cout<<"Y ";
	else
	cout<<"N ";
	}
	cout<<'\n';
	return 0;
	}

view raw [BaekJoon]_2629_양팔저울.cpp hosted with ❤ by GitHub