백준 16987. 계란으로 계란치기 (백트래킹)

https://www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

계란을 들고 깨지지 않은 계란을 깬다. 이때 계란을 깨는 순서에 대한 모든 경우를 확인해봐야 하기 때문에 백트래킹으로 문제를 푼다. 

 

1. 특징

1) 백트래킹을 잘 구현

 

2. 삽질 포인트

1) 조건 구현- "들고 있는 계란이 깨졌으면, 다음 계란을 든다."

if(_vec[cur].first <= 0 ) // 현재 들고 있는 계란이 깨졌으면
{ 
    func(cur+1); //다음 계란 든다
    return;
}

위의 코드로 해당 조건을 구현할 수 있는데, 내가 고민한 부분은 return;의 여부 였다. 

return값의 의미를 확인하기 위해 테스트 케이스 2번 상황을 가져왔다. 현재 0번 계란은 (1, 100) 1번 계란은 (8, 5) 2번 계란은 (3, 5)의 내구도와 무게를 가진다. 

1) cur == 0 이고, i == 1 이면 (i == 0이면 자기자신이라 continue로 이 경우 배제시켰기 때문에 i == 1)

_vec[0]의 내구도 = -4, _vec[1]의 내구도 = -92

그리고 func(1) 호출

2) cur == 1이면,

_vec[1]의 내구도 <= 0 이어서 func(2) 호출

3) cur == 2이면,

더이상 깰 계란이 없기 때문에 func(3) 호출한다

4) cur == 3이면,

 현재 깨진 계란 수로 max를 업데이트 한다. 

그리고 자신을 호출한 곳으로 돌아가서 그 뒤의 연산을 수행한다. 현재 자신을 호출한 함수는 더 이상 실행할 게 없어서 종료되고 이 함수를 호출한 곳으로 돌아간다. 

4) return 해서 2번으로 돌아가는데 

1번 다음 계란을 드는 것을 의미하는 func(2)를 호출한다. 

*여기서 return이 없다면, 깨져있는 깨진 1번을 들고, 다른 계란을 계속 찾는 행위를 하는 것을 의미한다. 그래서 이 코드에서 return을 빼면 1번 계란이 깨진 채로 2번 계란을 깨서 mx가 3이 나온다. 

*return이 있는 현재는, func(1)을 호출한 1번으로 돌아가서 0번 계란을 들고 2번 계란을 깨는 과정을 시작한다. 

 

2) 조건 구현 - 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 

if(cnt <= n-1 ) // 계란이 한개 빼고 다 깨졌으면
{ 
    func(cur+1); //다음 계란 든다
    return;
}

 

3. 코드

#include <string>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <vector>
using namespace std;

int n;
vector<pair<int, int>> _vec; // 계란의 내구도, 계란의 무게
int mx;
int cnt; //깨진 계란수
void func(int cur) // cur은 들고있는 계란의 index
{
    if(cur == n)  // 마지막 계란까지 확인했으면 끝
    {
        mx = max(mx, cnt);
        return;
    }
    
    if(_vec[cur].first <= 0 || cnt == n-1)
    {
        func(cur+1);
        return;
    } // 현재 들고 있는 계란이 깨졌으면, 또는 현재 계란이 한 개 빼고 다 깨졌으면 다음 계란 든다
    
    for(int i = 0; i < n; i++)//들어있는 계란을 순회함.(0번부터 ~ n-1번까지의 계란)
    {

        if(cur == i) continue; // 자기 자신을 깨려고 하면
        if(_vec[i].first <= 0) continue; // 깨려고 하는 계란 계졌으면, 다음 계란을 꺤다. 
        
        _vec[cur].first -= _vec[i].second;
        _vec[i].first -= _vec[cur].second;
        if(_vec[cur].first <= 0) cnt++;
        if(_vec[i].first <= 0) cnt++;

        func(cur+1);
        if(_vec[cur].first <= 0) cnt--;
        if(_vec[i].first <= 0) cnt--;
        _vec[cur].first += _vec[i].second;
        _vec[i].first += _vec[cur].second;
        
    }

}

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

    int s, w;
    for(int i = 0; i < n; i++)
    {
        cin >> s >> w;
        _vec.push_back(make_pair(s, w));
    }

    func(0);
    cout << mx;
}