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

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

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 주어진 추들로 특정 무게를 측정할 수 있냐 없냐를 구해야 하는 문제이다.

   먼저, 추의 갯수와 무게가 주어진다면 어떤 무게들을 구할 수 있는지 부터 생각해보자.

   예를 들어서 1g, 5g 짜리 추 2개가 있다고 생각해보자.

   이 2개의 추로 알 수 있는 무게는 무엇이 있을까???

   1. 2개의 추를 합한 6g 추를 알아낼 수 있을 것이다.

   2. 1개의 추만 이용해서 1g, 5g 를 알아낼 수 있을 것이다.

   3. 2개의 추를 서로 다른 양팔저울에 올림으로써 4g의 추를 알아낼 수 있을 것이다. (1g + 4g = 5g)

  

    즉, 위의 3가지 경우를 모두 구해보면 된다.

2) 위의 3가지 경우를 구하는 방식에 대해서 알아보자. 본인은 재귀를 통해서 구하는 방법을 사용하였다.

void Make_Weight(int Cnt, int Result)
{
    if (Cnt > N) return;
    if (Visit[Cnt][Result] == true) return;
 
    Visit[Cnt][Result] = true;
 
    Make_Weight(Cnt + 1, Result + Weight[Cnt]);
    Make_Weight(Cnt + 1, Result);
    Make_Weight(Cnt + 1, abs(Result - Weight[Cnt]));
}

   위 처럼 구현을 하였는데, 코드에 대해서 설명을 하자면... 가장 먼저 (0,0)으로 위의 함수가 호출되어진다.

   그리고 조건문에서는, 재귀를 탈출할만한 조건인 추의 갯수가 N개를 넘는경우와, 이미 알아낸 추의 무게라면

   그대로 종료하도록 구현하였다. 처음 만나는 무게라면 Visit배열을 통해서 체크를 해 주었다.

   그리고 위의 3가지에 대해서 재귀를 구현하였다.

   1. 추의 갯수를 증가시키면서 (Cnt + 1) 무게를 더해주는 (Result + Weight[Cnt]) 재귀.

     → 구슬과 반대편에 추를 올리는 Case.

   2. 추의 갯수를 증가시키면서 아무런 무게도 더해주지 않는 재귀.

     → 구슬이 추의 무게와 같을 경우 구하는 Case.

   3. 추의 갯수를 증가시키면서, 무게를 빼주는 재귀.

     → 구슬과 같은편에 올림으로써 추들간의 차이를 구하는 Case.

[ 소스코드 ]

#include<iostream>
#include<cmath>
 
#define endl "\n"
#define MAX 30
using namespace std;
 
int N, M;
int Weight[MAX];
int Find[7];
bool Visit[MAX + 1][MAX * 500 + 1];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Weight[i];
    }
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> Find[i];
    }
}
 
void Make_Weight(int Cnt, int Result)
{
    if (Cnt > N) return;
    if (Visit[Cnt][Result] == true) return;
 
    Visit[Cnt][Result] = true;
 
    Make_Weight(Cnt + 1, Result + Weight[Cnt]);
    Make_Weight(Cnt + 1, Result);
    Make_Weight(Cnt + 1, abs(Result - Weight[Cnt]));
}
 
void Solution()
{
    Make_Weight(0, 0);
    for (int i = 0; i < M; i++)
    {
        if (Find[i] > MAX * 500) cout << "N ";
        else if (Visit[N][Find[i]] == true) cout << "Y ";
        else cout << "N ";
    }
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}