[백준/C++] 계란으로 계란치기 (No. 16987)

문제

문제 설명

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 봤을 때 가장 효율적인 방법이 있을까? 고민했지만 방법이 떠오르지 않았다.

그래서 완전 탐색으로 모든 경우를 고려해 계란을 깨는 방법을 선택했다.

 

이러한 방법이 가능한 이유는 N이 8로 작기 때문에 8^8 = 2^24로 충분히 빠르게 해결이 가능하기 때문이다.

 

1번 계란부터 차례대로 다른 계란을 치는데 만약 깨져있다면 넘어가도록 코드를 구현했다.

 

이 과정에서 내구도와 무게가 저장된 vector가 계속 복사되지 않도록 Call by Reference를 이용했다.

 

i번 계란으로 j번 계란을 칠 수 있다면 i번 계란과 j번 계란의 내구도를 각각 줄이고 내구도가 0보다 작으면 계란이 깨져있으므로 깬 계란 수에 더했다.

 

이렇게 N번 계란까지 전부 계란을 치는데 성공했다면, 그 때까지 깨진 계란의 수를 비교해 업데이트 하도록 코드를 구현했다.

 

 

[아이디어 정리]

1. 1번 계란부터 N번 계란까지 다른 계란을 치도록 완전 탐색으로 코드를 구현한다.
2. 만약 i번 계란으로 j번 계란을 칠 수 있다면, i번 계란과 j번 계란의 내구도를 깎고 계란이 깨졌는지를 반영한 다음 i+1번째 계란으로 넘어간다.
3. 만약 i번 계란으로 j번 계란을 칠 수 없다면 치지 않고 바로 i+1번 계란의 차례로 넘어간다.
4. N번 계란까지 완료했다면 그 동안 깨진 계란의 수를 비교해 최대값을 갱신한다.

 

 

 

Code

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include <cmath>
#include <queue>
using namespace std;

int maxAns = 0;

void DFS(int deepth, vector<pair<int, int>> &V, int& N, int breakEgg)
{
	if (deepth == N) {
		maxAns = max(maxAns, breakEgg);
		return;
	}
	if (V[deepth].first <= 0)
	{
		DFS(deepth + 1, V, N, breakEgg);
	}
	else {
		int n;
		for (int i = 0; i < N; i++) {
			if (i!=deepth) {
				if (V[i].first > 0) 
				{
					n = 0;
					V[deepth].first -= V[i].second;
					V[i].first -= V[deepth].second;
					if (V[i].first<=0)
					{
						n += 1;
					}
					if (V[deepth].first <= 0) {
						n += 1;
					}
					DFS(deepth + 1, V, N, breakEgg+n);
					V[deepth].first += V[i].second;
					V[i].first += V[deepth].second;
				}
				else {
					DFS(deepth + 1, V, N, breakEgg);
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	int N;
	cin >> N;
	// 내구도, 무게
	vector<pair<int, int>> V(N);
	int a, b;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		V[i]={a,b};
	}
	DFS(0, V, N, 0);
	cout << maxAns;

	return 0;
}

---

 

처음에 i번 계란이 깨져서 넘어가는 경우는 고려했지만, 반대로 i번 계란으로 칠 수 있는 계란들이 없는 경우를 고려하지 않았다.

 

다행히 빠르게 반례를 찾아 문제를 해결할 수 있었다.

 

문제 푸는게 게을러 지는 것 같은데 슬슬 아침형 인간이 되어야되나...

 

 

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