[ 백준 16987 ] 계란으로 계란치기 (C++)

백준의 계란으로 계란치기(16987) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제를 먼저 이해해보고 어떻게 접근해야할지 생각해보자.

   계란으로 계란을 내리쳐서 최대로 몇 개의 계란까지 깰 수 있는지 구해야 하는 문제이다.

   계란을 깨는 규칙? 조건? 이 문제에 제시되어 있는데 이를 간단한 설명과 함께 적어보겠다.

   1. 가장 왼쪽 계란을 든다. → 무조건 가장 왼쪽 계란으로 시작을 한다.

   2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나

     깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을

     진행한다.

     → 손에 들고 있는 계란이 아직 깨지지 않았고, 다른 계란들 중 하나라도 계란이 살아있다면

        그 계란을 내려치고 그 다음 계란을 손에 쥔다.

   3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이

      가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

      → 가장 마지막 계란이 될 때까지 계란을 내려치는 것을 반복한다.

   간단하게 적어보자면 위와 같다. 본인은 이 부분을 DFS로 구현해 주었다.

    DFS의 탐색 조건은 '모든 계란을 다 돌아보면서, 칠 수 있는 계란이 있으면, 계란을 내려치고 그 다음 계란으로

    DFS호출' 과 같다. 그리고 또 하나의 예외적인 상황에 대해서 설명을 하자면 바로 윗줄에서 말했던 모든 계란을 다

    돌아보는데, 이 과정에서 더 이상 칠 수 있는 계란이 없다면 마지막 계란을 바로 호출해 버림으로써 탐색을 종료하도록

    구현해 주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, Answer;
int Weight[MAX];
int Duration[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Duration[i] >> Weight[i];
    }
}
 
void DFS(int Idx)
{
    if (Idx >= N)
    {
        int Cnt = 0;
        for (int i = 0; i < N; i++)
        {
            if (Duration[i] <= 0) Cnt++;
        }
        if (Answer < Cnt) Answer = Cnt;
        return;
    }
 
    if (Duration[Idx] <= 0) DFS(Idx + 1);
    else
    {
        bool Flag = false;        // 내려쳤는지 안쳤는지 판단
        for (int i = 0; i < N; i++)
        {
            if (i == Idx || Duration[i] <= 0) continue;
 
            Duration[Idx] = Duration[Idx] - Weight[i];
            Duration[i] = Duration[i] - Weight[Idx];
            Flag = true;
            DFS(Idx + 1);
            Duration[i] = Duration[i] + Weight[Idx];
            Duration[Idx] = Duration[Idx] + Weight[i];
        }
        if (Flag == false) DFS(N);
    }
}
 
 
 
void Solution()
{
    DFS(0);
    cout << Answer << 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;
}