[BOJ] 16987번 : 계란으로 계란치기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int eggs[8][2];
bool isBroken[8]; 
int N;
int maxCount;

void backTrack(int current_pos) {
	if (current_pos == N) {
		int count = 0;
		for (int i = 0; i < N; i++) {
			if (isBroken[i] == 1) count++;
		}
		maxCount = max(count, maxCount);
		return;
	}
	if (isBroken[current_pos]) {
		backTrack(current_pos + 1);
		return;
	}
	bool anyUnbroken = false;
	for (int i = 0; i < N; i++) {
		if (current_pos == i || isBroken[i]) continue;

		anyUnbroken = true;

		if (!isBroken[i]) {
			eggs[i][0] -= eggs[current_pos][1];
			eggs[current_pos][0] -= eggs[i][1]; 

			if (eggs[current_pos][0] <= 0) isBroken[current_pos] = 1;
			if (eggs[i][0] <= 0) isBroken[i] = 1;

			backTrack(current_pos + 1);

			eggs[i][0] += eggs[current_pos][1];
			eggs[current_pos][0] += eggs[i][1];
			isBroken[current_pos] = (eggs[current_pos][0] <= 0);
			isBroken[i] = (eggs[i][0] <= 0);
		}
	}
	if (!anyUnbroken) {
		backTrack(current_pos + 1);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 2; j++) cin >> eggs[i][j];
	}
	backTrack(0);
	cout << maxCount << '\n';

}

 

 

3. solution 2 :

// 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;  
}

source code 출처 : https://github.com/codenamegyoungho/basic-algo-lecture/blob/master/0x0C/solutions/16987.cpp

basic-algo-lecture/0x0C/solutions/16987.cpp at master · codenamegyoungho/basic-algo-lecture

바킹독님은 내구도와 무게를 따로따로 관리를 했음. 그리고 이제 손에 집어든 계란이 깨져있거나, 손에 집어든 계란만 안 깨졌을 때는 다음번을 호출하며, return 한다. 다음에 또 풀어야겠다.