BOJ 2629. 양팔저울

BOJ 2629. 양팔저울

랭크 : 골드3

문제 풀이

dp를 통해, 이전까지의 가능한 무게값을 배열에 다 저장해두고, 이를 바탕으로 새로 들어온 무게추의 크기를 더하거나 빼거나, 그대로 두면서 가능한 조합을 모두 뽑아냅니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N, M, tmp;
int board[31][80'001];

int main() {
    int MAXX = 0;
    fastio;
    cin >> N;
    board[0][40'000] = 1;
    for (int i=0; i<N; i++) {
        cin >> tmp;
        for (int j= -MAXX; j<= MAXX; j++) {
            if (board[i][40'000 + j]) {
                board[i+1][40'000 + j] = 1;
                if (40'000 + j - tmp >= 0) board[i+1][40'000 + j - tmp] = 1;
                if (j + tmp <= 40'000) board[i+1][40'000 + j + tmp] = 1;
            }
        }
        MAXX = min(MAXX + tmp, 40'000);
    }

    cin >> M;
    for (int i=0; i<M; i++) {
        cin >> tmp;
        if (board[N][40'000 + tmp] || board[N][40'000 - tmp]) cout << "Y ";
        else cout << "N ";
    }
    cout << endl;
}

알고리즘	시간복잡도	공간복잡도
dp	$O(N*M)$	$O(N*M)$