백준 16987 계란으로 계란치기 c++ // 백트래킹, 원상복구, 다음깊이로 넘어가는 방법

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

16987번: 계란으로 계란치기

 

1. 다음깊이로 넘어가는 방법

if(조건){
	go(k+1);
    return;
}

하면된다.

 

2. 의사코드

 

3. 내 전체코드

#include <bits/stdc++.h>
using namespace std;

int n, v[10], ret;
vector<pair<int, int>> eggs;

//현재 k번째 계란을 들고 깨려고함
void go(int k) {
	if (k >= n) {
		int died_count = 0;
		for (auto p : eggs) {
			//cout << p.first << " ";
			if (p.first <= 0) died_count++;
		}
		//cout << "\n";

		ret = max(ret, died_count);
		return;
	}

	//들고있는계란이 깨진경우
	if (eggs[k].first <= 0) {
		go(k + 1);
	}
	else {
		//때릴대상
		bool on = false;
		for (int i = 0; i < n; ++i) {
			if (i == k) continue; //자기자신은 못때림
			if (eggs[i].first <= 0) continue; //깨진계란은 못때림

			on = true;
			eggs[k].first -= eggs[i].second;	//계란깨기
			eggs[i].first -= eggs[k].second;
			go(k + 1);//다음번째 계란을 들기
			eggs[k].first += eggs[i].second;	//원복
			eggs[i].first += eggs[k].second;

		}
		//때릴대상이 없는경우
		if(!on) go(k + 1);
	}

}

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

	//1. 드는계란 idx : 0~n-1
	//2. 치는계란 : n-1 C 1

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		eggs.push_back({ a,b });
	}

	//계란집기
	go(0);

	cout << ret;
}

 

4. 바킹독 아이디어

cnt로 깨진 계란수를 저장한다.

원복의 조건문은 똑같이 한다.

 

5. 바킹독 (의사)코드

들고잇는계란이 깨짐 or 깰계란이없음 -> go(a+1), return

나머지경우 : 깨고, go(a+1) , 원복

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/550e5f94d9504613971281134eebaeae
#include <bits/stdc++.h>
using namespace std;
int n;
int s[10],w[10];
int mx = 0;
int cnt = 0; // 깨져있는 계란의 수

void solve(int a){ // a번째 계란으로 다른걸 깰 차례
  if(a == n){
    mx = max(mx,cnt);
    return;
  }
  if(s[a] <= 0 or cnt == n-1){
    solve(a+1);
    return;
  } // a번째 계란이 깨져있거나 다른 모든 계란이 깨져있으면 넘어감
  for(int t = 0; t < n; t++){ // t번째 계란을 내려치고 싶다
    if(t == a or s[t] <= 0) continue;
    s[a] -= w[t];
    s[t] -= w[a];
    if(s[a] <= 0) cnt++;
    if(s[t] <= 0) cnt++;
    solve(a+1);
    if(s[a] <= 0) cnt--;
    if(s[t] <= 0) cnt--;    
    s[a] += w[t];
    s[t] += w[a];
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> s[i] >> w[i];
  }
  solve(0);
  cout << mx;  
}