양팔저울


작성일 : 2017-01-21 03:05:24
조회수 : 3464



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


$dp[i][j] = i$번 째 추를 사용할 때, 무게가 $j$인 경우


예를 들어


1,1,3,4,2 의 추가 존재한다고 한다면


1+1+3, 1+4 의 경우로 5번째까지 올 수 있습니다. 이 경우 그 뒤의 추가 중복되어서 계산되므로 이를 메모이제이션하여 시간을 단축할 수 있습니다.


$i$번 째 추에 대해서는


1) 이 추만을 사용하는 경우

2) 이 추를 사용하지 않는 경우

3) 이 추를 누적하여 사용하는 경우


의 3가지로 나누어 볼 수 있습니다.


그 뒤 중요한 것이, 구슬이 올라갈 위치의 저울에도 추를 올릴 수 있으므로 구슬의 무게+임의의 추의 무게 의 합에 대한 무게를 잴 수 있는지 체크하여 1번이라도 잴 수 있다면 Y를 출력하면 됩니다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

int n, m, k, ps, w[31];
bool dp[31][150001];
void dfs(int pos, int wei)
{
    if (pos == n || dp[pos][wei]) return;

    dp[pos][wei] = true;
    dfs(pos + 1, w[pos+1]);
    dfs(pos + 1, wei);
    dfs(pos + 1, wei + w[pos+1]);
}
int main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> w[i], ps += w[i];
    dp[n - 1][0] = true;
    dfs(0, w[0]);
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> k;
        bool f = false;

        for (int j = 0; j <= ps; j++)
        {
            if (j + k > ps) break;
            if (dp[n - 1][j] && dp[n - 1][j + k])
            {
                f = true;
                break;
            }
        }
        cout << (f ? "Y " : "N ");
    }
}

양팔저울 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글