[2629] 양팔 저울

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

이 문제가 어려운 이유는 반대쪽 저울에 추를 올릴 수 있다는 점입니다.

문제의 예제처럼 1과 4의 추가 있을 때 검사할 수 있는 무게는

0, 1, 4

그리고

(1 + 4), (4 - 1)

이렇게 다섯가지 입니다. 어려운 부분은 (4 - 1)이겠죠.

문제의 조건을 보면 추의 최대 개수 30개, 추의 최대 무게 500g, 확인할 무게 최대 7개입니다.

dp정의는 dp[n][k] = n번 추까지 사용했을 때 k라는 무게를 만들 수 있는지 (bool) 입니다.

n번째 추에서 나눠지는 경우는 세가지가 있습니다. 추를 왼쪽 저울에 올릴지, 안올릴지, 아니면 오른쪽 저울(편의상 검사할 무게를 오른쪽)에 올릴지 입니다.

이렇게 한다면 시간복잡도는 30개 * 3가지 경우 * 15000(500g * 30)입니다만... 저는 dp배열을 30001로 잡았습니다.

이유는 -값도 저장하기 위해서입니다. dp[][15000]이 0의 무게를 나타내며 14999는 -1, 15001은 1입니다. 30000이면 15000이겠죠??

아래는 풀코드입니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
bool dp[31][30001];
int weight[31];
int m[3] = {-1, 0, 1};
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i = 1; i <= n; i++) scanf("%d", &weight[i]);
 
    dp[0][15000] = 1; // 0은 추가 없어도 만들 수 있음.
    for(int i = 1; i <= n; i++) // i번째 추
    {
        for(int j = 0; j < 3; j++)//-1, 0, 1
        {
            for(int k = 0; k <= 30000; k++) // -15000 ~ 15000
            {
                int tt = weight[i] * m[j] + k; // k무게에다가 해당 추를 왼쪽 혹은 오른쪽저울에 올리던지 아니면 안올리던지
                dp[i][tt] += dp[i - 1][k]; // i - 1번째 인덱스까지 k무게가 존재한다면 dp[i][tt]도 존재하게 됨.
            }
        }
    }
 
 
    int nn;
    scanf("%d", &nn);
 
    for(int i = 0; i < nn; i++)
    {
        int ret;
        scanf("%d", &ret);
        printf("%c ", dp[n][ret + 15000] ? 'Y' : 'N');
    }
 
    puts("");
    return 0;
}