문제

설명

입출력

반성

아주 간단한 DP인데, 배워야 할 점이 있다.
나는 음수가 나오는 경우를 없애기 위해 한쪽으로 몰아넣고 +, -로 해결하려고 했다.
그래도 음수가 나오는 경우가 생길 수 있었다. 테스트케이스는 음수를 고려하고 들어오는게 아니기 때문에.
이 점을 5달 전에 알게되었지만, 코드를 보니 또 같은 방식으로 틀렸더라.

문제점

시작이 0이라고 할 때,
저울의 오른쪽에 무게를 추가하면 +, 왼쪽에 무게를 추가하면 -라고 하자.
이 때, 왼쪽에 무게를 추가하면 -로 변한다. 여기서 오류가 있었다.

중요한 사실은 양팔저울은 방향이 정해져있지 않다는 것이다.
왼쪽으로 기울었더라도(-로 변했더라도) 반대쪽에서 바라보면 오른쪽으로 기울어진 것과 같다.

아이디어

내가 보려고 작성하는 내용들이라 건너뛰는 내용이 있을 수 있다.

생각의 편의를 위해 기준이 되는 추는 일단 제외하고 고려해보자
혹은 마지막에 올린다고 생각해보자.

이 상태가 기준점이므로 저울이 영점인 상태가 된다.
이제 오른쪽이나 왼쪽에 추를 놓아가면서 우 무게 = 좌 무게로 만들면 되는것.

이런식으로 말이다. 이 때는 영점보다 + 되었다고 할 수 있다.

그러나 다음 경우도 있을 수 있다.

이렇게 되면 영점보다 - 되었다고 할 수 있다.

음수인 무게는 없지만, 우리는 변수가 음수가 되는 경우를 고려하기 위해 그렇게 해보자.

우리는 어떤 추가 어떤 순서로 올려졌는지는 관심이 없다. 단지 총량만 고려하고 있을 뿐이다.

총량을 따지자면, 다음처럼 된 것과 같다고 볼 수 있다.

우리가 바라던대로 2의 차이를 표현했으며, 반대편에 기준 추인 2를 놔주면 끝난다.
기준 추는 처음부터 반대편에 있었다고 할 수 있다.

저울을 뒤집었다고 생각하면 편할 수 있다.

따라서 음수가 나올 수 있는 경우 절대값을 씌워주면 위의 절차와 같은 효과를 가질 수 있다.

코드

// 2022.03.11 15:48:49
// 2629 https://boj.kr/2629
#include <bits/stdc++.h>
using namespace std;
int weight[31];
int dp[31][15001];

int n, tw;
int f(int wi, int sum)
{
    if (sum == tw)
        return 1;
    if (wi >= n)
        return 0;
    int &ret = dp[wi][sum];
    if (ret != -1)
        return ret;

    int onLeft = f(wi + 1, abs(sum - weight[wi]));
    // 뒤집혀도 총량만 같으면 같은문제다.
    int onRight = f(wi + 1, sum + weight[wi]);
    int skip = f(wi + 1, sum);
    return ret = skip || onLeft || onRight;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> weight[i];

    int tc;
    cin >> tc;
    while (tc--)
    {
        memset(dp, -1, sizeof(dp));
        cin >> tw;
        cout << (f(0, 0) ? 'Y' : 'N');
        if (tc)
        	cout << ' ';
    }
}