[ SWEA 1486 ] 장훈이의 높은 선반 (C++)

SWExpertAcademy의 장훈이의 높은선반(1486 / D4) 문제이다.

[ 문제풀이 ]

주어진 점원들 중에서 높이가 B인 선반 위에 있는 물건을 꺼낼 수 있게 탑을 만들었을 때, 점원의 키의 총 합과 선반의 높이의

차이를 최소로 만드는 값을 구해야 하는 문제이다.

본인은 문제를 보고 가장 먼저 조합을 생각했다. 왜냐하면, 점원들의 키는 무조건 합치는 것이기 때문에 순서와 상관이 없다.

예를 들어서, 키가 3인 점원을 첫 번째로 뽑고, 키가 5인 점원을 두 번째로 뽑은 경우와, 키가 5인 점원을 첫 번째로 뽑고

키가 3인 점원을 두 번째로 뽑는 경우를 보게 되면 결과는 똑같이 8이 된다. 순서에 따라서 결과가 달라지지 않는 상황이기

때문에 조합을 생각해보았다.

조합을 아직 잘 모른다면 아래의 글을 참고하도록 하자.

[ 조합 알아보기(Click) ]

그렇다면, 이 문제에서 조합을 구현할 때, 종료조건을 생각해보자. 일반적인 조합을 구하는 문제들의 경우, 우리가 원하는

특정 갯수만큼 선택을 하게 되면, 원하는 결과 및 계산을 하게 되고 종료를 하게 되는데, 이 문제에서는 어떤 경우가 될까?

일단, 특정 x명을 뽑는 개념으로 접근을 할 수는 없다. 무조건 사람 수가 적다고 해서 문제의 정답이라는 보장은 없기 때문이다.

그래서 본인은 조합을 구하는 DFS함수의 매개변수로 "현재까지 뽑은 점원들의 키의 총 합" 을 가지고 다녔는데,

계속 선택하는 과정에서, 이 매개변수의 값이 'B'보다 크거나 같다면 그 차이를 기존의 답과 비교하고 갱신해주는 방식으로

구현하였다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, B, Answer;
int Employee[MAX];
bool Select[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    memset(Select, false, sizeof(Select));
    Answer = 987654321;
}
 
void Input()
{
    cin >> N >> B;
    for (int i = 0; i < N; i++)
    {
        cin >> Employee[i];
    }
}
 
void DFS(int Idx, int Sum)
{
    if (Sum >= B)
    {
        int Diff = Sum - B;
        Answer = Min(Answer, Diff);
        return;
    }
 
    for (int i = Idx; i < N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(i, Sum + Employee[i]);
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(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;
}