[BOJ]16987-계란으로 계란치기

16987

#include <iostream>
#include <vector>

using namespace std;

int N;
int Max = 0;

vector<pair<int, int>> eggs;

void res()
{
    int cnt = 0;
    for (pair<int, int> item : eggs)
    {
        if (item.first <= 0)
        {
            cnt++;
        }
    }

    if (cnt > Max)
    {
        Max = cnt;
    }
}

void dfs(int depth)
{
    if (depth > N)
    {
        return;
    }


    for (int i = 0; i < N; i++)
    {
        if (eggs[depth].first <= 0)
        {
            dfs(depth + 1);
        }
        else if (depth == i || eggs[i].first <=0)
        {
            continue; 
        }
        else
        {
            eggs[depth].first -= eggs[i].second;
            eggs[i].first -= eggs[depth].second;

            dfs(depth + 1);

            eggs[depth].first += eggs[i].second;
            eggs[i].first += eggs[depth].second;    
        }
    }

    res();

    return;
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int dur, weight;
        cin >> dur >> weight;
        eggs.push_back({ dur, weight });
    }

    dfs(0);

    cout << Max;

    return 0;
}

시행착오

#include <iostream>
#include <vector>

using namespace std;

int N;
int Max = 0;

vector<pair<int, int>> eggs;
vector<bool> cracked;

void res()
{
    int cnt = 0;
    for (bool item : cracked)
    {
        if (item)
        {
            cnt++;
        }
    }

    if (cnt > Max)
    {
        Max = cnt;
    }
}

void dfs(int depth)
{
    if (depth == N)
    {
        res();
        return;
    }

    if (cracked[depth])
    {
        dfs(depth + 1);
        return;
    }

    for (int i = 0; i < N; i++)
    {
        if (depth == i)
        {
            continue;
        }

        if (cracked[i])
        {
            continue; 
        }
        else
        {
            eggs[depth].first -= eggs[i].second;
            eggs[i].first -= eggs[depth].second;
            if (eggs[depth].first <= 0)
            {
                cracked[depth] = true;
            }

            if (eggs[i].first <= 0)
            {
                cracked[i] = true;
            }

            //cout << depth << '/' << i << endl;
            dfs(depth + 1);

            eggs[depth].first += eggs[i].second;
            eggs[i].first += eggs[depth].second;
            if (eggs[depth].first > 0)
            {
                cracked[depth] = false;
            }

            if (eggs[i].first > 0)
            {
                cracked[i] = false;
            }

            
        }
    }

    dfs(depth + 1);

    return;
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int dur, weight;
        cin >> dur >> weight;
        eggs.push_back({ dur, weight });
        cracked.push_back(false);
    }

    dfs(0);

    cout << Max;

    return 0;
}

시간 초과로 해답을 보니 알고리즘은 비슷했으나 자료형에 저장하는 작업을 거치지 않아서 빨랐다.

참고자료

---

16987 c++ 풀이