백준 17610 양팔저울 (C++)

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

#include <iostream>
#include <vector>

using namespace std;

vector<int> g;
int ans = 0;
int k;

bool visit[2600005];



void gram(int cnt, int w) {

    if (cnt == k) {
        if (w > 0) {
            visit[w] = true;
        }
        return;
    }

    gram(cnt + 1, w);
    gram(cnt + 1, w + g[cnt]);
    gram(cnt + 1, w - g[cnt]);

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> k;

    g.resize(k);

    int sum = 0;

    for (int i = 0; i < k; i++) {
        cin >> g[i];
        sum += g[i];
    }

    gram(0, 0);

    for (int i = 1; i <= sum; i++) {
        if (!visit[i]) {
            ans++;
        }
    }

    cout << ans;

    return 0;
}

1. 문제

k개의 서로 다른 추가 주어진다. 이들과 양팔 저울을 사용하여 1부터 k개 추의 합 까지의 무게의 물을 재려고 할 때, 양팔 저울을 한 번만 사용하여 측정할 수 없는 무게의 개수를 출력하라.

2. 풀이

브루트포스 문제이다. k개의 모든 추를 어떻게 사용하느냐에 따라 경우를 나눌 수 있는데, 그 경우는 다음과 같다.

1. 해당 추를 사용하지 않는 경우
2. 해당 추를 물과 같은 위치에 놓는 경우
3. 해당 추를 물과 다른 위치에 놓는 경우

void gram(int cnt, int w) {

    if (cnt == k) {
        if (w > 0) {
            visit[w] = true;
        }
        return;
    }

    gram(cnt + 1, w);
    gram(cnt + 1, w + g[cnt]);
    gram(cnt + 1, w - g[cnt]);

}

해당 코드이다. 0번 추부터 k-1번 추까지의 모든 추에 대하여 위에 적은 경우를 재귀로 돌린다. 모든 추를 다 돌았을 때 해당 무게가 양수라면 이를 기록한다.

    int sum = 0;

    for (int i = 0; i < k; i++) {
        cin >> g[i];
        sum += g[i];
    }
 
    gram(0, 0);

    for (int i = 1; i <= sum; i++) {
        if (!visit[i]) {
            ans++;
        }
    }

해당 연산이 끝나고, 1부터 모든 추의 합 까지 중 한 번에 무게를 잴 수 없다면(!visit[i]) 이를 세어준다. 이 ans를 출력하면 정답을 구할 수 있다.