2022.10.13.TIL (알고리즘,못 품)

백준 문제풀이

2629번

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

2629번: 양팔저울

배낭문제

 

재귀로 해결해야 함

사용한 추의 갯수와 추의 총 무게만 생각하여 만들 수 있는 무게들을 구함

추를 모두 사용했을 때 ture인지 false인지 확인

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
int weight;
int wss[30];
int ball;
int bs[7];

bool dp[31][15001] = { 0, };

void canMake(int n, int w) {
	if (n > weight || dp[n][w]) return;
	dp[n][w] = true;
	canMake(n + 1, w + wss[n]);//추를 오른쪽에 올림
	canMake(n + 1, abs(w - wss[n]));//추를 왼쪽에 올림
	canMake(n + 1, w);//추를 안씀
}

int main() {
	cin >> weight;
	for (int i = 0; i < weight; i++) cin >> wss[i];
	cin >> ball;
	for (int i = 0; i < ball; i++) cin >> bs[i];
	
	canMake(0, 0);

	for (int i = 0; i < ball; i++) {
		if (bs[i] > 15000) cout << "N ";
		else if (dp[weight][bs[i]]) cout << "Y ";
		else cout << "N ";
	}
}