16987 계란으로 계란치기

문제 링크

문제를 이해를 잘못하여 푸는데 너무나 많은 시간을 허비하였다. 출제자가 좀 더 명쾌하게 문제의 설명을 적었으면 좋겠다는 생각이 들었다.

퍼즐은 일렬로 놓여있는 계란에 대해 왼쪽부터 차례로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨는 문제였다. 구체적으로 계란을 치는 과정을 설명하면 아래와 같다.

위의 설명에서 ‘한 번씩만 다른 게란을 쳐 최대한 많은 계란을 깨는 문제…’라는 부분에서 헷갈려서 한 계란을 여러 계란을 친다고 이해하여 이상한 풀이를 작성하게 되었다. 문제 자체는 쉬웠지만 이해하지 못해 너무 아쉬웠다. 그리고 bump3의 코드가 맞는 풀이인데 마지막 부분 ret == 0인 경우를 생각하지 못해 한 번 틀렸었다. (마지막 계란이 치는 곳이 없는경우)

ps. cnt 부분에서 오버헤드가 많이 걸리므로 함수에서 최대값을 전달하면 좀 더 빠른 코드를 작성할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int en[8], w[8], hit[8][8];

int cnt()
{
    int ret = 0;
    for (int i = 0; i < N; i++)
    {
        if (en[i] <= 0)
            ret += 1;
    }

    return ret;
}

int bump(int idx)
{
    /*static int a;
    cout << a++ << "\n";*/

    if (idx == N)
        return cnt();

    if (en[idx] <= 0)
        return bump(idx + 1);

    int ret = 0;

    for (int i = 0; i < N; i++)
    {
        if (en[i] <= 0 || i == idx || hit[idx][i])
            continue;

        en[i] -= w[idx];
        en[idx] -= w[i];
        hit[idx][i] = 1;
        
        if (en[idx] <= 0)
            ret = max(bump(idx + 1), ret);
        else
            ret = max(bump(idx), ret);

        en[i] += w[idx];
        en[idx] += w[i];
        hit[idx][i] = 0;

        if (ret != 0)
            cout << ret << "\n";
    }

    if (!ret)
        ret = cnt();

    return ret;
}

int bump2(int idx)
{
    if (idx == N)
        return cnt();

    if (en[idx] <= 0)
        return bump2(idx + 1);

    int ret = 0;
    vector<int> a, b, tmp;
    for (int i = 0; i < N; i++)
    {
        if(en[i] > 0 && i != idx)
            a.push_back(i);
    }

    do
    {
        for (int c : a)
        {            
            en[c] -= w[idx];
            en[idx] -= w[c];
            hit[idx][c] = 1;
            b.push_back(c);
            if (en[idx] <= 0)
            {
                tmp.assign(en, en + N);
                ret = max(bump2(idx + 1), ret);
                break;
            }
        }

        if (en[idx] > 0)
        {
            tmp.assign(en, en + N);
            ret = max(bump2(idx + 1), ret);
        }

        for (int r : b)
        {
            
            hit[idx][r] = 0;
            en[r] += w[idx];
            en[idx] += w[r];
        }
        b.clear();

        if (ret != 0)
            cout << ret << "\n";
    } while (next_permutation(a.begin(), a.end())); 

    return ret;
}

// idx의 계란이 터질떄까지 다른 계란을 때린다. 
// 하지만 한번씩 치기로 정해졌기때문에 불가능하다.
int bump3(int idx)
{
    if (idx == N)
        return cnt();

    if (en[idx] <= 0)
        return bump3(idx + 1);

    int ret = 0;

    for (int i = 0; i < N; i++)
    {
        if (en[i] <= 0 || i == idx)
            continue;

        en[i] -= w[idx];
        en[idx] -= w[i];

        ret = max(ret, bump3(idx + 1));

        en[i] += w[idx];
        en[idx] += w[i];
    }

    if (ret == 0)
        return cnt();

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> en[i] >> w[i];
    
    cout << bump3(0) << "\n";
}

빠른 풀이

#include <iostream>
#include <algorithm>
using namespace std;

int n, cnt;
int arr[9][2];

void DFS(int d, int a[][2], int c) {
    int tmp[9][2], t;

    for (int i = 0; i < n; i++) {
        tmp[i][0] = a[i][0];
        tmp[i][1] = a[i][1];
    }

    for (int i = 0; i < n; i++) {
        if (i == d || a[i][0] <= 0)
            continue;
        else {
            t = c;
            tmp[d][0] -= tmp[i][1];
            tmp[i][0] -= tmp[d][1];
            if (tmp[d][0] <= 0)
                t++;
            if (tmp[i][0] <= 0)
                t++;
            cnt = max(cnt, t);
            for (int j = d + 1; j < n; j++) {
                if (tmp[j][0] > 0) {
                    DFS(j, tmp, t);
                    break;
                }
            }
            tmp[d][0] = a[d][0]; tmp[i][0] = a[i][0];
        }
    }
}

int main() {
    cnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i][0] >> arr[i][1];
    }

    DFS(0, arr, 0);
    cout << cnt;
}