계란으로 계란치기

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N;
pair<int,int> in;
vector<pair<int,int>> v(10);
int ans=0;
bool isbreak[10];
void func(int cur, int tot){
    int endCnt = 0;
    bool end = false;
    for(int i=0;i<N;i++)
        if(!isbreak[i]) endCnt++;
    if(endCnt <= 1) end = true;
    /* 모든 계란을 다 돌았거나, 남은 계란이 1개 이하이면 종료 */
    if(cur == N || end)
    {
        ans = max(ans, tot);
        return;
    }else if(isbreak[cur]){
        /* 현재 계란이 깨져있으면 다음 계란으로 넘어가게 함 
           --> 이 예외를 아래 for에서 처리하면 그냥 끝나버림 */
        func(cur+1,tot);
    }
    else{
        for(int i=0;i<N;i++)
        {
            if(cur == i || isbreak[i]) continue; 
            v[cur].first -= v[i].second;
            v[i].first -= v[cur].second;
            int t=0;
            if(v[cur].first <= 0) {
                t++;
                isbreak[cur] = true;
            }
            if(v[i].first <= 0) {
                t++;
                isbreak[i] = true;
            }
            func(cur+1, tot+t);
            /* 원상복귀를 해야 이번 계란을 안치고 다음 계란을 친 경우를 계산할 수 있음 */
            v[cur].first += v[i].second;
            v[i].first += v[cur].second;
            isbreak[cur] = false;
            isbreak[i] = false;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
        cin >> v[i].first >> v[i].second;
    func(0,0);
    cout << ans;
    return 0;
}

• 어려웠던 점
  • 문제 이해를 잘못함
  • 문제에 처리해야 할 예외가 나와있는 것은 좋은것
  • 문제가 많다고 대충읽지 말고, 꼼꼼하게 읽고 이해하고 처리하기

• key point!
  1) 전형적인 백트래킹 로직의 원리를 지켜줘야 한다
      --> 내가 한 행위를 원상복귀 하는 과정이 항상 필요
  2) 현재 들고있는 계란이 깨진경우 예외처리 필요
  3) 남은 계란이 1개 이하이면 종료하는 조건 필요