양팔저울( BOJ 17610 )

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

17610번: 양팔저울

 

문제 파악하기

양팔저울을 사용하여 측정할 수 없는 물의 무게가 몇 개인지 찾아내는 문제입니다. 양팔저울은 딱 1번 사용할 수 있으며, 물을 담을 수 있는 접시는 왼쪽 혹은 오른쪽 상관없이 올릴 수 있습니다. 우리는 추의 개수가 최대 13개라는 점에 주목하면 문제를 해결할 실마리를 찾을 수 있습니다.

 

문제 해결하기

추의 개수가 최대 13개라면 나올 수 있는 모든 경우의 수는 총 3¹³ = 1,594,323가지 있습니다. 각각의 추는 왼쪽 혹은 오른쪽 혹은 어느 곳에도 두지 않은 경우까지 총 3가지의 경우의 수를 가지고 있으며, 이런 추가 최대 13개 있을 수 있기 때문에 총 3¹³ = 1,594,323가지 경우의 수가 나오게 됩니다. 이정도 숫자라면 1초 안에 탐색이 가능합니다!

 

그럼 모든 경우의 수를 탐색해봅시다. 현재 양팔저울과 추의 현황을 상태로 만들면 우리는 모든 경우의 수를 탐색할 수 있습니다. 우선, 현재 사용할 추의 개수가 필요합니다. 그래야 탐색을 언제 끝낼 수 있을지 알 수 있습니다. 그리고 양팔저울의 왼쪽과 오른쪽에 올라간 추의 합을 저장해야 합니다. 그래야 탐색이 끝났을 때, 측정할 수 있는 물의 양을 알 수 있기 때문입니다. 따라서, 우리는 다음과 같은 상태함수를 만들 수 있습니다.

sv( idx, left, right ) // idx: 추의 번호 / left: 왼쪽에 올라간 추의 합 / right: 오른쪽에 올라간 추의 합

 

위의 함수를 작성하였으면 남은 일은 모든 경우의 수를 탐색하는 일입니다. 탐색의 종료 조건과 다음 상태를 적절하게 설정하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#define NMAX 15
#define VMAX 200000
using namespace std;
 
int K, t;
vector< int > v;
 
int tot, ret;
int check[NMAX*VMAX];
 
int abs(int k) { return k>0?k:-k; }
 
void sv(int idx, int left, int right) {
    if(idx == K) check[abs(left-right)] = 1;
    else {
        sv(idx+1, left, right);
        sv(idx+1, left+v[idx], right);
        sv(idx+1, left, right+v[idx]);
    }
}
 
int main() {
    // input
    scanf("%d", &K);
    for(int i=0;i<K;i++) {
        scanf("%d", &t);
 
        v.push_back(t);
        tot += t;
    }
 
    // solve
    sv(0, 0, 0);
 
    // check
    for(int i=0;i<=tot;i ++) ret += (1-check[i]);
 
    printf("%d", ret);
}

후기

완전탐색을 연습하기 적절한 문제라고 생각합니다. 함수를 떠올리기 쉬울 뿐더러 별다른 코너 테스트케이스도 없어 간단하게 구현할 수 있어 연습문제로 적절한 문제로 보여집니다.