[백준 16987] 계란으로 계란치기 C++

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

16987번: 계란으로 계란치기

문제풀이

 

계란으로 계란치기 문제의 경우, 글을 해석하느라 시간이 조금 오래걸렸습니다. 

 

생각 보다 문제에 도움이 안되는 말이 앞에 주절주절이 있고, 중간 설명하는 부분에 중요 포인트가 많은데

처음 읽었을 때 확실하게 안와닿는 부분이 많았습니다. 

 

먼저, 문제에서 말한대로 계란의 정보를 가져오는데,

저는 struct로 대입했습니다. (뭔가 구조안에 넣어서 체계적으로 만들고 싶은 생각?)

 

struct 안에는 power라는 내구성에 대한 변수가 있고, 상대 계란을 깰 때 사용하는 weight의 변수도 있습니다.

이 struct를 변수화 시켜서

typedef를 사용하여 egg라는 구조체를 배열로 만들었습니다.

 

문제에서 나온대로, '손에 든 계란이 깨졌거나, 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다' 라는 조건에서 

if (eggs[dep].power <= 0) return dfs(dep + 1);

위의 코드와 함께,

	bool None_FLAG = false;



	for (int j = 0; j < n; j++) {
		int i = dep;

		if (i == j) continue;

		if (eggs[j].power > 0) {
			None_FLAG = true;

			
			eggs[i].power -= eggs[j].weight;
			eggs[j].power -= eggs[i].weight;

			dfs(dep + 1);

			eggs[i].power += eggs[j].weight;
			eggs[j].power += eggs[i].weight;
		}



	}

	if (!None_FLAG) return dfs(dep + 1);

FLAG를 선언하여 한번이라도 내구성이 양인 값을 찾지 못하면 다음 인덱스로 넘어가게 설정했습니다.

 

위에 코드를 보면, None_FLAG = false가 되어있는데, for 문을 다 돌렸음에도 불구하고 None_FLAG = true안에 못들어가게 되면, 

 

	if (!None_FLAG) return dfs(dep + 1);

위 코드를 선언해주어 다음 index에 넘어가도록 만들었습니다.

 

이렇게 코드를 짜면, 문제에서 말한 '손에 든 계란이 깨졌거나, 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다' 조건에 충족시킬 수 있습니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <algorithm>

using namespace std;

#define input_max 8 + 1

typedef struct egg{
	int power;
	int weight;
} Eggs;

int n;
int result;


Eggs eggs[input_max];

void dfs(int dep) {

	if (dep == n) {

		
		int sum = 0;

		for (int i = 0; i < n; i++) {
			if (eggs[i].power <= 0) sum++;
		}

		result = max(result, sum);

		return;
	}

	if (eggs[dep].power <= 0) return dfs(dep + 1);



	bool None_FLAG = false;



	for (int j = 0; j < n; j++) {
		int i = dep;

		if (i == j) continue;

		if (eggs[j].power > 0) {
			None_FLAG = true;

			
			eggs[i].power -= eggs[j].weight;
			eggs[j].power -= eggs[i].weight;

			dfs(dep + 1);

			eggs[i].power += eggs[j].weight;
			eggs[j].power += eggs[i].weight;
		}



	}

	if (!None_FLAG) return dfs(dep + 1);
		
}


void solution() {

	cin >> n;

	for (int q = 0; q < n; q++) {
		cin >> eggs[q].power;
		cin >> eggs[q].weight;
	}


	dfs(0);

	

	cout << result << '\n';
	
}
int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);
	cout.tie(0);
	
	solution();

	return 0;
}