백준[2629] 양팔저울

풀이 방법

dp[i][j] : i번째 추까지 사용했을 때 무게 j를 만들 수 있는지 여부

i번째 상태는 i - 1번째 상태에 i번째 무게만큼 더할 것인지 뺄 것인지 아무것도 안 할 것인지로 정의할 수 있다.

 

코드

무게가 음수인 경우를 커버하기 위해 40000을 기본값으로 했다.

#include <cstdio>

int weight[32];
bool dp[32][80004];
int main() {
    int N; scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", weight + i);

    dp[0][40000] = true;

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 80000; j++) {
            if (!dp[i - 1][j]) continue;
            dp[i][j] = true;
            if (j + weight[i] <= 80000) dp[i][j + weight[i]] = true;
            if (j - weight[i] >= 0) dp[i][j - weight[i]] = true;
        }
    }
    int T; scanf("%d", &T);
    while (T--) {
        int input; scanf("%d", &input);
        if (dp[N][input + 40000]) printf("Y ");
        else printf("N ");
    }
}

 

문제 링크: www.acmicpc.net/problem/2629