[BOJ] 2629번 양팔저울

Sol1) DP

추를 쓸지 안쓸지로 생각하면 2^30이기 때문에 백트래킹으로는 안 풀린다는 것이 느껴집니다. N이 애매한 수치인데 배낭문제 아닐까 생각하게 됩니다.

 

추가 1g, 4g이 있다고 가정해봅시다.

1g만 있을 때는 1만 체크할 수 있습니다.

4g이 추가적으로 들어온다면 4-1, 4+1, 4, 1을 체크할 수 있습니다.

 

1. DP[i][j] = DP[i - 1][j + arr[i])) // j = 1, arr[i] = 4

2. DP[i][j] = DP[i - 1][abs(j - arr[i])] // j = 1, arr[i] = 4 -> 4  - 1

3. DP[i][j] = DP[i - 1][j] // i - 1번째에서 성공한 모든 경우는 i번째 추를 안쓰면 되기 때문에 다 됩니다.

4. DP[i][arr[i]] = true

 

소스 코드

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int MAXN = 35;
bool DP[MAXN][40005]; // 개수, 무게
int arr[MAXN];

int main(){
    FASTIO;
    
    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    DP[0][arr[0]] = true;
    for (int i = 1; i < n; i++){
        DP[i][arr[i]] = true;
        for (int j = 1; j <= 40000; j++){
            if (DP[i - 1][j]) DP[i][j] = true;
            else if (DP[i - 1][abs(j - arr[i])]) DP[i][j] = true;
            else if (DP[i - 1][j + arr[i]]) DP[i][j] = true;
        }
    }
    
    cin >> m;
    for (int i = 0; i < m; i++){
        int num; cin >> num;
        if (DP[n - 1][num]) cout << "Y ";
        else cout << "N ";
    }
    return 0;
}