[ SWEA 3234 ] 준환이의 양팔저울 (C++)

SWExpertAcademy의 준환이의 양팔저울(3234 / D4) 문제이다.

[ 문제풀이 ]

저울에 무게추를 하나씩 올릴 때, 어느 한 순간이라도 "오른쪽에 올라가 있는 무게의 합이 왼쪽에 올라가 있는 합보다 커져서는 안되게" 만들어야 한다.

문제에 나와있듯이 양팔저울 위에 올리는 순서는 총 N ! 개가 존재하고, 어느 쪽에 올릴지 결정해야 하므로 2^N 만큼이 걸리므로

최악의 경우를 계산해보면 N = 9일 때, 9 ! x 2^9 만큼의 시간이 걸리게 된다. 이렇게 되면 시간초과를 면할 수가 없다.

따라서 본인은 '더 이상 탐색을 해보지 않아도 되는 경우' 를 적절히 걸러주는 과정을 하나 추가해 주었다. 이 과정은 밑에서 천천히 알아보도록 하자.

가장 먼저 본인은 문제를 보고 순열을 구현하였다. 왜냐하면 무게추를 올리는 순서에 따라서 결과가 달라질 것이기 때문에 가장 먼저 순열을 구현하였다. 순열에 대해 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 순열 구현하는 법 알아보기 (Click) ]

그럼 위의 순열을 이 문제에 맞게 바꿔보도록 하자. 먼저, 추는 무조건적으로 '왼쪽'에 먼저 올려주는 것이 좋다.

왜냐하면 왼쪽의 무게는 항상 오른쪽의 무게보다 작아서는 안되기 때문이다. 그럼 오른쪽에 올려주는 경우는 언제일까 ??

바로 "현재 양팔저울의 상태에서 무게추를 어느 한 쪽에 올리려고 하는데, 그 추를 오른쪽에 올리더라도 왼쪽의 무게가 오른쪽의 무게보다 더 클 경우" 에만 오른쪽에 무게추를 올려주었다.

for (int i = 0; i < N; i++)
{
    if (Select[i] == true) continue;
    Select[i] = true;
    DFS(Cnt + 1, Left + Arr[i], Right);
 
    if (Right + Arr[i] <= Left) DFS(Cnt + 1, Left, Right + Arr[i]);
    Select[i] = false;
}

즉 ! 위와 같이 단순히 순열을 이용해서 원소를 뽑는데, line 7)과 같은 조건이 성립할 때만, 오른쪽에 무게추를 올려주었다.

결과적으로 보면, 우리가 순열을 이용해서 무게추를 순차적으로 하나씩 뽑아가면서 무게추를 양팔저울의 왼쪽이든 오른쪽이든

올릴건데, "왼쪽의 무게가 오른쪽의 무게보다 크거나 같다" 라는 규칙을 지키면서 뽑는 것이다.

하지만 위와 같이 구현하더라도 시간초과가 발생한다. 그래서 본인은 "탐색을 해도 되지 않아도 되는 경우" 한 가지를 더 만들어 주었다. 지금부터 이 경우에 대해서 알아보자.

예를 들어서 { 1, 2, 3, 4, 10 } 으로 무게추가 주어진 상황을 가정해보자.

그리고 가장 처음으로 '10'의 무게를 가진 무게추를 왼쪽 저울에 올렸다고 가정해보자.

그럼 현재 저울의 상태는 왼쪽저울 = 10 , 오른쪽 저울 = 0 이 될 것이다. 그리고 우리에게 남은 선택지는 4개가 더 있다.

그럼 위의 4개를 어느 추는 왼쪽에도 올려보고 어느 추는 오른쪽에도 올려보고, 한쪽에만 다 올려보고, 반대쪽 한쪽에만 다 올려보고... 하는 과정이 과연 필요할지에 대해서 생각을 해보자.

왼쪽 저울의 무게 = 10 이다. 나머지 4개의 추가 모두 오른쪽으로 간다고 하더라도, 규칙에 어긋나지 않는다.

왜냐하면 나머지 4개의 추가 모두 오른쪽으로 가게되면 오른쪽 저울의 무게 = 1 + 2 + 3 + 4 = 10 으로 10 >= 10 이기 때문에

규칙에 어긋나지 않는다.

그럼, 모두 오른쪽으로 가는 것이 아닌, 일부만 오른쪽에 올리고 일부는 왼쪽저울에 올리는 경우를 생각해보자.

과연 "왼쪽저울의 무게는 항상 오른쪽 저울의 무게보다 크거나 같아야 한다." 라는 규칙이 어긋나는 경우가 발생할까 ??

나머지 4개의 추를 몇 개를 왼쪽에 올리든, 몇 개를 오른쪽에 올리든 규칙에 어긋나는 경우는 존재하지 않는다.

즉 ! 이런 경우는 더 이상의 탐색이 필요하지 않다는 것이다. 왜 ?? 위에서 봤듯이, 어떻게 올리더라도 규칙에 어긋나는 경우가 없기 때문에 실제로 올려볼 필요 없이, 위의 4개의 추를 "어떻게 올리는지에 대한 경우의 수"만 계산해 주면 되기 때문이다.

그럼 이 경우의 수를 어떻게 계산할까 ?? 정말 친절하게도 문제에 나와있다.

N 개의 추를 양팔저울에 올릴 때 발생할 수 있는 경우의 수 = N ! * 2^N 이라고...

아마 4개의 추를 양팔저울에 올릴 때 발생할 수 있는 경우의 수는 4 ! * 2^4 일 것이다. 즉 ! 이 만큼의 경우의 수만 정답의 갯수에 더해주고, 실제로 무게추를 하나하나씩 뽑아가면서 양팔저울에 올려보는 탐색을 더 이상 할 필요가 없게 된다.

그럼, 현재 상태가 위에서 말한 경우에 해당하는 상태인지 어떻게 판단할까 ??

먼저, 우리가 알고 있어야 할 정보들 부터 한번 나열해보자.

1. 저울의 왼쪽에 올려져 있는 무게.

2. 남은 무게추들의 총 무게

우리는 이 2개의 정보를 가지고 위의 경우인지 아닌지 판단할 수 있다.

첫 번째 정보인 '저울의 왼쪽에 올려져 있는 무게' 는 반드시 알고 있어야 하는 값이다. 그래야지 오른쪽저울에 무슨 추를 더 올리든 말든 계산을 할 수 있기 때문이다.

두 번째 정보인 '남은 무게추들의 총 무게'는 한번 생각해보자. 분명히 위의 상황에서도 1 + 2 + 3 + 4 <= 10 이라는 이유로 더 이상 탐색을 하지 않아도 되는 경우라는 것을 판단했다. 즉 ! '1 + 2 + 3 + 4' 라는 "남은 추들의 무게의 총 합"을 알고 있었기 때문에

이런 계산이 가능했다. 따라서, 남은 무게추들의 총 무게를 알아야 한다.

본인은 위의 정보를 구하기 위해서 "무게추들의 총 합" 을 입력과 동시에 구해놨다.

왜냐하면 "남은 무게추들의 총 합" 은 "무게추들의 총 합 - 저울의 왼쪽에 올려져 있는 무게" 로 구할 수 있기 때문이다.

따라서, "무게추 들의 총 합"을 미리 구해놓고 순열을 구하는 과정에서,

"저울의 왼쪽에 올려져 있는 무게 >= 무게 추들의 총 합 - 왼쪽에 올려져 있는 무게" 가 성립한다면 더이상의 탐색 없이

경우의 수만 구해주었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 9
using namespace std;
 
int N, Sum, Answer;
int Arr[MAX];
bool Select[MAX];
 
int Exp[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };
int Factorial[] = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
 
void Initialize()
{
    Answer = 0;
    Sum = 0;
    memset(Select, false, sizeof(Select));
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
        Sum = Sum + Arr[i];
    }
}
 
// 오른쪽에 올라가 있는 추가 왼쪽보다 더 작거나 같아야 한다.
void DFS(int Cnt, int Left, int Right)
{
    if (Cnt == N)
    {
        Answer++;
        return;
    }
    if (Left >= Sum - Left)
    {
        Answer = Answer + Exp[N - Cnt] * Factorial[N - Cnt];
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(Cnt + 1, Left + Arr[i], Right);
 
        if (Right + Arr[i] <= Left) DFS(Cnt + 1, Left, Right + Arr[i]);
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(0, 0, 0);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}