[ SWEA 8275 ] 햄스터 (D4)

SWExpertAcademy의 햄스터(8275) 문제이다.

[ 문제풀이 ]

모든 경우의 수를 탐색하더라도 N과 X의 값이 작기 때문에 충분히 시간내에 해결이 가능하다.

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

최악의 경우, 6개의 햄스터 우리에 대해서 각 우리마다 0마리부터 10마리 까지 넣어보는 경우를 계산해야 하는데

이 경우에도 11^6 으로 약 177만개의 경우의 수가 발생하므로 충분히 시간내에 해결이 가능하다.

그래서 본인은 중복순열을 구현함으로써 햄스터 우리에 들어가 있는 햄스터의 수를 구현해 주었다.

중복순열을 구현한 이유는 먼저 순서에 영향을 미치기 때문이다. 예를 들어서 3개의 햄스터 우리가 존재하고, 이 때 각 우리에

[ 1, 2, 3 ] 이렇게 햄스터가 들어가 있는 경우와, [ 3, 2, 1 ] 이렇게 들어가 있는 경우는 다른 결과를 초래하기 때문에

순열을 이용한 것이다. 두 번째는 중복이 허용된다는 것이다. 1번 햄스터 우리에 2마리의 햄스터가 들어가 있다고 생각해보자.

그렇다면, '2'마리의 햄스터가 1번햄스터 우리게 있따는 이유로, 2번 햄스터 우리에는 '2'마리가 절대로 중복적으로 존재하면

안될까 ?? 아니다. 모든 우리에 똑같은 햄스터 수가 들어가 있는 경우도 분명히 존재할 것이다.

따라서 중복 순열을 이용해서 구현해 주었다. 중복순열에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 중복순열 알아보기(Click) ]

문제의 정답을 출력하기 위해서는 3가지 조건이 필요하다.

1. 햄스터를 배치할 수 있는 방법이 여러가지일 경우, 햄스터 수가 가장 많은 방법을 출력한다.

2. 1번 조건이 여러가지일 경우, 사전순으로 앞선 것을 출력한다.

3. 1번 조건, 2번조건을 모두 만족시키지 못한다면 -1을 출력한다.

먼저 1번 조건을 위해서 중복순열을 구현하는 재귀함수에 "사용한 가장 많은 햄스터 수"를 매개변수로 두어서 계산해 주었다.

즉, 햄스터를 배치할 수 있는 경우가 발생했을 때, 기존의 사용한 햄스터 수와 비교를 해서 더 크다면 갱신해 주는 방식으로

진행하였따.

2번 조건은 따로 구현하지는 않았다. 왜냐하면, 각 우리에 햄스터의 수를 설정해 줄 때, 0마리부터 X마리까지 순차적으로

넣어주었기 때문에, 따로 구현하지 않더라도 사전순으로 경우의 수가 발생하도록 구현해 주었다.

3번 조건은 모든 경우의 수가 탐색이 끝난 후에 최종 정답을 나타내는 배열에 정확한 값이 들어있지 않으면 해당 조건을

만족하는 경우의수가 없다고 판단해서 -1을 출력해 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define N_MAX 7
#define INF 2e9
using namespace std;
 
int N, X, M, Sum_Max;
int Num[N_MAX];
int Answer[N_MAX];
vector<pair<pair<int, int>, int>> Cmd;
 
void Initialize()
{
    memset(Num, 0, sizeof(Num));
    memset(Answer, -1, sizeof(Answer));
    Cmd.clear();
    Sum_Max = -INF;
}
 
void Input()
{
    cin >> N >> X >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Cmd.push_back(make_pair(make_pair(a, b), c));
    }
}
 
bool Check()
{
    /* 조건을 만족하는지 판단하는 함수. */
    for (int i = 0; i < Cmd.size(); i++)
    {
        int L = Cmd[i].first.first;
        int R = Cmd[i].first.second;
        int Cnt = Cmd[i].second;
 
        int Sum = 0;
        for (int j = L; j <= R; j++) Sum = Sum + Num[j];
        
        if (Sum != Cnt) return false;
    }
    return true;
}
 
void DFS(int N_Num, int Sum)
{
    /* N_Num = 햄스터 우리의 번호 */
    /* Sum = 햄스터의 수 */
    if(N_Num == N + 1)
    {    
        /* 모든 우리에 햄스터 수를 설정해 주었을 때 */
        if (Check() == true)
        {
            if (Sum > Sum_Max)
            {
                /* 설정한 햄스터 수를 기존의 설정한 수와 비교해서 더 크다면 갱신. */
                Sum_Max = Sum;
                for (int i = 1; i <= N; i++) Answer[i] = Num[i];
            }
        }
        return;
    }
    
    /* 중복 순열 */
    for (int i = 0; i <= X ; i++)
    {
        Num[N_Num] = i;
        DFS(N_Num + 1, Sum + i);
    }
}
 
void Solution()
{
    DFS(1, 0);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        bool Flag = true;
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " ";
        for (int i = 1; i <= N; i++)
        {
            /* 정확하지 않은 값이 정답을 나타내는 배열에 들어있는 경우. */
            /* 조건에 맞는 경우가 없다는 것을 의미. = -1을 출력 */
            if (Answer[i] == -1)
            {
                cout << -1 << endl;
                Flag = false;
                break;
            }
        }
        if (Flag == true)
        {
            for (int i = 1; i <= N; i++) cout << Answer[i] << " ";
            cout << endl;
        }
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}