[백준/C,C++] 2629번: 양팔저울

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

2629번: 양팔저울

플이

티스토리 꾸준함님의 풀이를 참고하여 풀었습니다.

 

추를 구슬이 없는 쪽에 올릴지, 구슬이 있는 쪽에 올릴지, 아무 곳에도 올리지 않을지

 

3가지의 경우를 재귀 호출하며 풀 수 있는 문제입니다.

 

두번째 예제인

 

4

2 3 3 3

3

1 4 10

 

으로 예를 들어보겠습니다.

 

 

2, 3, 3, 3의 추 중에 두번째 추까지를 올린다고 해봅시다.

 

빨간색의 경우 추를 구슬이 없는 쪽에 올리는 경우, 흰색의 경우 올리지 않는 경우,

 

파란색의 경우 구슬의 반대쪽에 올리는 경우라고 했을 때, 확인할 수 있는 무게는 위와 같습니다.

 

여기서 중복되는 값이 많이 생기는데 해당 중복을 동적 계획법을 사용해 방지할 수 있습니다.

 

#include <iostream>

using namespace std;

const int MAX_CNT = 30;
const int MAX_WEIGHT = 500;

int N, M;
int W[MAX_CNT];
bool cache[MAX_CNT + 1][MAX_CNT * MAX_WEIGHT + 1];

void func(int cnt, int weight)
{
    // 기저 사례 (추를 이미 다 올렸거나, 갱신된 값인 경우)
    if (cnt > N || cache[cnt][weight]) {
        return;
    }

    cache[cnt][weight] = true;

    // 구슬이 있는 쪽에 추를 올리는 경우
    func(cnt + 1, weight + W[cnt]);
    // 추를 올리지 않는 경우
    func(cnt + 1, weight);
    // 구슬이 없는 쪽에 추를 올리는 경우
    func(cnt + 1, abs(weight - W[cnt]));
}

int main(void)
{
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> W[i];
    }

    func(0, 0);

    cin >> M;

    for (int i = 0; i < M; i++) {
        int T; cin >> T;
        if (T > MAX_CNT * MAX_WEIGHT) {
            cout << "N ";
            continue;
        }
        cache[N][T] ? cout << "Y " : cout << "N ";
    }

    return 0;
}

반례

Input

10
5 6 2 3 9 10 4 7 11 13
10
34 12 41 21 35 13 28 29 33 24

Output

Y Y Y Y Y Y Y Y Y Y