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

백준의 양팔저울(17610) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 무게 추들을 이용해서 한번만에 측정할 수 없는 무게가 몇 가지가 있는 구해야 하는 문제이다.

본인은 완전탐색을 이용해서 문제에 접근해 보았다.

 

무게 추를 양팔저울에 올리는 방법은 다음과 같이 크게 2가지가 존재한다.

1. 현재 무게추를 올리지 않고, 그 다음 무게추로 넘어가는 방법

2. 현재 무게추를 올리고, 그 다음 무게추로 넘어가는 방법

크게 보면 이렇게 2가지만 존재하게 된다.

그런데 위의 Case에서 2번 Case를 한번 살펴보자.

2. 현재 무게추를 올리고, 그 다음 무게추로 넘어가는 방법

현재의 무게추를 올리게 된다면, 무게는 그 만큼 더해질 것이다.

예를 들어서, 현재 양팔저울에 올려져 있는 무게가 Ag 이고, 현재 올리려는 무게추가 Bg이라면 양팔저울에 올려져 있는 무게는

(A + B)g 이 될 것이다. 하지만 ! 우리는 여기서 (A + B)g 말고 또 다른 무게를 알 수 있다.

바로, (A - B)g 이다. 양팔저울의 어느 한쪽에 올려져 있는 무게가 Ag이고 반대편에는 빈 그릇이 있을 것이다. 이 때, 빈 그릇과 함께 Bg을 올리고 이 양팔저울이 수평이 맞을 때 까지 물을 붓게 된다면, 이 물은 (A - B)만큼 부을 수 있게 될 것이다.

즉 ! (A - B)또한 탐색이 가능하다는 것을 의미한다.

 

따라서, 양팔저울에 무게추를 올리는 방법은 다음과 같이 정리할 수 있다.

1. 현재 무게추를 올리지 않고 , 그 다음 무게추로 넘어가는 방법

2. 현재 무게추를 빈 그릇과 반대편에 올리는 방법

3. 현재 무게추를 빈 그릇과 함께 올리는 방법

 

이를 재귀를 통해서 표현하면 다음과 같이 표현할 수 있다. 그리고 여기서 무게의 음수는 존재하지 않으므로, 음수는 잘못된 계산이라 판단하고 그냥 넘어가 주었다.

 

[ 소스코드 ]

#include <iostream>
#include <vector>
 
#define MAX 15
using namespace std;
 
int K, Sum;
int Arr[MAX];
vector<bool> Measure;
 
void Input()
{
    cin >> K;
    for(int i = 0; i < K; i++) 
    {
        cin >> Arr[i];
        Sum += Arr[i];
    }
    Measure.resize(Sum + 1, false);
}
 
void DFS(int Idx, int Weight)
{
    if(Idx == K)
    {
        if(Weight >= 0) Measure[Weight] = true;
        return;
    }
 
    DFS(Idx + 1, Weight);
    DFS(Idx + 1, Weight + Arr[Idx]);
    DFS(Idx + 1, Weight - Arr[Idx]);
}
 
void Solution()
{
    DFS(0, 0);
 
    int answer = 0;
    for(int i = 1; i <= Sum; i++)
    {
        if(Measure[i] == false)
        {
            answer++;
        }
    }
    cout << answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    Solve();
    return 0;
}