boj 16987 계란으로 계란치기

 

1. 문제 :https://www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

2. 문제에서 원하는 것

계란을 왼쪽에서 오른쪽으로 한 칸씩 움직이며 맨 오른쪽 끝에 있는 계란 까지 손에 들고

다른 임의의 계란을 들어서 부딪혔을 때 계란을 최대 몇 개 깰 수 있는가?

 

3. 적용할 알고리즘

총 계란의 개수가 8개이므로 계란을 들고 어떤 계란과 부딪힐지 모든 경우의 수를

조사하면 총 연산 횟수는 대략 최대 7의 8승(5,764,801)이 되어서

백트래킹을 이용한 완전 탐색이 가능하다.

 

4. 수학적 사고, 새로운 발상

필요 없음, 그냥 단순한 백트래킹

 

5. 코드

#include<iostream>
#include<string>
#include<stack>
#include<tuple>
#include<queue>
#include<algorithm>
#include<bitset>

using namespace std;

int n;

pair<int, int> egg[10];

int ans = 0;

void solve(int cur)
{
    if (cur == n)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            //cout << egg[i].first << ' ';
            if (egg[i].first <= 0) cnt++;
        }
        ans = max(ans, cnt);
        return;
    }

    if (egg[cur].first <= 0)
    {
        solve(cur + 1);
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (cur == i) continue;
        if (egg[i].first <= 0) continue;

        egg[cur].first -= egg[i].second;
        egg[i].first -= egg[cur].second;
        solve(cur + 1);
        egg[cur].first += egg[i].second;
        egg[i].first += egg[cur].second;
    }

    if (cur == n - 1) solve(cur + 1);
}

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

    cin >> n;
    
    for (int i = 0; i < n; i++) cin >> egg[i].first >> egg[i].second;

    solve(0);

    cout << ans;
}

6. 느낀 점

쉬운 문제인데 문제 잘못읽어서 1시간 동안 뻘짓했다ㅋㅋ

앞으로는 문제를 잘 읽고 풀이가 확실히 떠오를 때 구현을 시작하자...