[백준,c++] 16987번 - 계란으로 계란치기

문제

16987번: 계란으로 계란치기

 

코드

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

int N, ans, temp_cnt;
vector<pair<int,int>>v;

void backtracking(int idx){
    if(idx == N+1) return;
    
    for(int i=0; i<N; i++){
        if(v[idx].first<=0) backtracking(idx+1);
        else if(v[i].first<=0 || i==idx) continue;
        else{
            v[idx].first -= v[i].second;
            v[i].first -= v[idx].second;
            backtracking(idx+1);
            v[idx].first += v[i].second;
            v[i].first += v[idx].second;
        }
    }
    
    for(int i=0; i<N; i++){
        if(v[i].first<=0) temp_cnt++;
    }
    ans = max(ans, temp_cnt);
    temp_cnt = 0;
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    for(int i=0; i<N; i++){
        int a, b; cin>>a>>b;
        v.push_back({a,b}); // {내구도, 무게}
    }
    
    backtracking(0);
    
    cout<<ans;
}

 

풀이

1. 가장 왼쪽의 계란을 든다.
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

위 조건에 맞게 백트랙킹을 돌리면 되는 문제입니다.

1번 조건을 만족하기 위해 첫 백트랙킹의 인덱스는 0번으로 주었고, 3번 조건을 만족시키기 위해 백트랙킹의 다음 인덱스는 현재 (계란 인덱스 +1)로 넣었습니다. 또한 2번 조건을 만족하기 위해서 조건문을 주어서 처리했습니다.