[C++] Boj 16987 계란으로 계란치기

문제 링크

16987 계란으로 계란치기

 

접근 및 알고리즘

문제를 이해하는 것만 해도 시간이 들었다. 나의 집중력 이슈 ㅜㅜ

문제 내용을 요약하자면 다음과 같다.

1. 입력으로 받은 계란 중 첫번째 계란을 손에 쥔다.
2. 남은 계란 중에 하나를 손에 쥔 계란으로 친다.
(손에 든 계란이 깨졌거나, 현재 계란 말고 다른 계란이 전부 깨져 있으면 치지 않는다.)
3. 이때, 손에 있는 계란이 깨질 수도 있고, 다른 계란이 깨질 수도 있고, 둘 다 깨질 수도 있다.
4. 아무튼 손에 있는 계란이 깨졌든 말든 한번 쳤으면 손에 있는 계란을 다시 제자리에 놓는다.
5. 그 다음에, 손에 있었던 계란의 다음 차례 계란을 손에 쥔다.
6. 2 - 5를 반복하고, 만약 방금 손에 쥐었던 계란이 마지막 위치의 계란이면 종료한다.

 

첫번째 계란 하나를 선택하고, 그 계란을 통해 생기는 모든 경우의 수를 백트래킹했다.

보통 백트래킹 문제와 비슷하게 계란이 깨졌는지 안 깨졌는지 확인하는 배열을 추가하여 풀었다.

 

문제가 길다고 당황하지 말고, 그냥 문제에 있는 알고리즘을 코드로 풀면 그만인 문제였다.

(난 당황했다 ㅋ)

 

코드

#include <iostream>
using namespace std;

struct Egg
{
    int DEF = 0;
    int ATK = 0;
};

int N = 0;
int ans = 0;
int cnt = 0;
int IsCrashed[10];
Egg eggs[10];

void Solve(int idx)
{
    // 마지막 계란까지 탐색 완료
    if (idx == N)
    {
        ans = max(ans, cnt);
        return;
    }

    // 현재 계란이 이미 깨졌다면 다음으로 이동
    // 현재 계란 말고 다른 계란이 전부 깨져 있으면 치지 않고 다음으로 이동
    if (IsCrashed[idx] || cnt == N - 1)
    {
        Solve(idx + 1);
        return;
    }

    for (int i = 0; i < N; i++)
    {
        // 자기 자신이나 깨진 계란 제외
        if (idx == i || IsCrashed[i])
        {
            continue;
        }

        eggs[idx].DEF -= eggs[i].ATK;
        eggs[i].DEF -= eggs[idx].ATK;

        if (eggs[idx].DEF <= 0)
        {
            cnt++;
            IsCrashed[idx] = true;
        }

        if (eggs[i].DEF <= 0)
        {
            cnt++;
            IsCrashed[i] = true;
        }
        
        Solve(idx + 1);

        // 원상 복구
        eggs[idx].DEF += eggs[i].ATK;
        eggs[i].DEF += eggs[idx].ATK;
        if (IsCrashed[idx])
        {
            cnt--;
            IsCrashed[idx] = false;
        }

        if (IsCrashed[i])
        {
            cnt--;
            IsCrashed[i] = false;
        }
    }
}


int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N;

    for (int i = 0; i < N; i++)
        std::cin >> eggs[i].DEF >> eggs[i].ATK;

    Solve(0);
    
    std::cout << ans;

    return 0;
}

 

시간 복잡도를 생각해 보면서 코드를 많이 수정해 보았다. 이 과정이 제일 재미있는 것 같다.