[BOJ] C++ 16987: 계란으로 계란치기 - 전형적인 백트래킹인지 판단하고 풀어보기

16987번: 계란으로 계란치기

 

예제가 굉장히 많아 백준에 들어가서 보시는 것을 추천합니다!

---

굉장히 재미있는 문제인데, 데이터의 수가 8로 굉장히 적다. 완전 탐색을 먼저 고려해 보고 문제에서 시키는 조건대로 알고리즘을 생각해 보자. 문제를 풀다가 알게 된 건데 1번 계란으로 3번을 깬 후 3번 계란으로 1번을 다시 깰 수 있다. 헷갈릴 것 같아서 이 조건은 먼저 기억해 두자.

 

문제의 조건을 따라서 계란을 깨다 보면 백트래킹 형태로 상태 공간 트리를 만들면서 구현하게 될 것 같다. 귀납적으로 접근하기도 쉬워 보이니 재귀로 구현해 보자.

 

기본 알고리즘은 1번 계란으로 깰 수 있는 거 다 깨보고 1 -> 2번 깬 케이스에서 2번 계란이 안깨졌다면 2번 계란으로 깰 수 있는거 다 깨 보는 방식으로 진행한다. 그런데 이 방식의 문제점이 하나 있다. 예제 1을 넣어서 돌려보면 1 -> 3 깨고 3만 깨진 상태에서 다음 스텝에서 1로 다시 2를 깨는건 구현할 수 없었는데, 간단하게 1 -> 3 깨고 다음 스텝에서 3번째 계란으로 다른 계란을 깨는걸 호출하는게 아니라 2번째 계란으로 다른 계란 깨는걸 호출해서 해결할 수 있었다. 다시 알고리즘을 생각해보면 1번 계란으로 깰 수 있는거 다 깨고 1 -> i를 깬 경우로 들어가서 2번 계란으로 깰 수 있는거 다 깨보는 방식이다. 함수 구조를 보자.

 

1. 함수 정의 : void func(int k) : k번째 계란으로 다른 계란 깨기
2. base condition
   1. k == n : 지금까지 깬 계란 수와 res를 비교하여 res 갱신
   2. k번째 계란이 깨진 상태 거나 계란을 다 깬 경우 func(k+1)을 호출하면 된다.
3. 재귀식
   1. 0~n번까지 계란 중 깰 수 있는 i번째 계란 선택
   2. i번째 계란을 충돌시키고 cnt, table 업데이트
   3. func(k+1) 호출
   4. func(k+1)이 끝났으면 i번째 계란을 충돌시킨 케이스를 다 본 것이므로 테이블과 cnt를 복원한다.

가장 헷갈리는 점이 재귀식에서 func(i)를 호출하는 게 아니라 func(k+1)을 호출해야 한다는 점이다.

 

/** BackTracking 16987 계란으로 계란치기 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n;
int table_hp[10];
int table_weight[10];
int res = 0;
int cnt = 0; // 깨진 계란 수

void func(int k)
{
    // k번째 계란으로 내려칠 차례이다.
    if (k == n)
    {
        res = max(res, cnt);
        return;
    }
    if (table_hp[k] <= 0 || cnt == n - 1)
    {
        func(k + 1);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (i == k || table_hp[i] <= 0)
            continue;
        table_hp[k] -= table_weight[i];
        table_hp[i] -= table_weight[k];
        if (table_hp[k] <= 0)
            cnt++;
        if (table_hp[i] <= 0)
            cnt++;
        func(k + 1);
        // 테이블 및 깨진 계란 수 복원
        if (table_hp[k] <= 0)
            cnt--;
        if (table_hp[i] <= 0)
            cnt--;
        table_hp[k] += table_weight[i];
        table_hp[i] += table_weight[k];
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> table_hp[i] >> table_weight[i];
    }
    func(0);
    cout << res;
}