[백준 17610번] 양팔저울

문제 링크

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

 

문제 요약

이 문제는 서로 다른 무게의 추 \(k\) 개가 주어졌을 때, 양팔저울을 한 번만 사용하여 1부터 주어진 추들의 무게의 합인 \(S\) 사이의 모든 무게 중 측정이 불가능한 무게의 개수를 구하는 문제이다.

 

문제 풀이

이 문제를 해결하기 위해서는 \(k\)개의 추를 가지고 만들 수 있는 모든 가능한 무게 조합을 고려하는 완전 탐색을 이용할 수 있다. 각 추에 대해 우리는 세 가지 선택을 할 수 있다.

1. 추를 사용하지 않는 경우
2. 양팔저울의 왼쪽에 올려놓는 경우
3. 양팔저울의 오른쪽에 올려놓는 경우

각 추를 위와 같은 세 가지 선택지 중 하나로 결정한 후, 양팔저울의 왼쪽과 오른쪽에 놓인 추들의 무게 차이를 계산한다. 이렇게 계산된 모든 가능한 무게를 boolean 배열에 기록한다. 이 배열은 특정 무게가 측정 가능한지 여부를 나타내는 배열이다. 마지막으로, 1부터 주어진 추들의 무게의 합인 \(S\)까지의 모든 무게를 순회하면서 boolean 배열에 기록되지 않은 무게의 수를 세면, 그 값이 바로 측정 불가능한 무게의 개수가 된다.

 

이 방법은 모든 경우의 수를 탐색하기 때문에 \(\mathcal {O}(3^k)\)의 시간복잡도를 가진다. 하지만 \(k\)가 최대 13밖에 되지 않기 때문에, 전체 경우의 수가 크지 않아 충분히 계산이 가능하다. 또한, 주어진 추들의 무게 합 \(S\)도 크지 않기 때문에 boolean 배열로 관리하기에 무리가 없다.

 

소스 코드

#include <stdio.h>
#include <stdlib.h>

int n, total, A[20];
bool isPossible[13 * 200010];

void func(int pos, int lsum, int rsum) {
    if (pos == n) {
        isPossible[abs(lsum - rsum)] = true;
        
        return;
    }
    
    func(pos + 1, lsum, rsum);
    func(pos + 1, lsum + A[pos], rsum);
    func(pos + 1, lsum, rsum + A[pos]);
}

int main() {
    scanf("%d", &n);
    
    for (int i = 0 ; i < n ; ++i) {
        scanf("%d", &A[i]);
        
        total += A[i];
    }
    
    func(0, 0, 0);
    
    int ans = 0;
    
    for (int i = 1 ; i <= total ; ++i) {
        if (!isPossible[i]) {
            ans += 1;
        }
    }
    
    printf("%d\n", ans);
}