[백준] 16987번 계란으로 계란치기

문제: 16987번: 계란으로 계란치기

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>
#include <sstream>

using namespace std;

int maxCnt = -1;
int n;
pair<int, int> eggs[8]; // max 가 8

void Funct(int idx) {
	// 마지막 계란에 도달했으면 빠져 나가기
	if (idx >= n) {
		int tmpCnt = 0;

		for (int i = 0; i < n; i++)
			if (eggs[i].first <= 0)
				tmpCnt++;

		if (tmpCnt > maxCnt)
			maxCnt = tmpCnt;

		return;
	}

	// 현재 계란이 깨졌는지 확인. 깨졌으면 다음 계란을 집어들어.
	if (eggs[idx].first <= 0) 
		Funct(idx + 1);
	else {
		// 현재 계란 안 깨졌으면 얘로 계란 쳐
		// 자기 자신이랑 이미 깨진 계란 제외하고
		bool flag = false; // 내려쳤는지 안쳤는지 판단
		for (int i = 0; i < n; i++) {
			if (i == idx || eggs[i].first <= 0) continue;

			// 계란끼리 부딪히면 내구도 깎임
			eggs[i].first -= eggs[idx].second;
			eggs[idx].first -= eggs[i].second;

			Funct(idx + 1);

			eggs[i].first += eggs[idx].second;
			eggs[idx].first += eggs[i].second;
		}

		// 칠 계란이 없으면 걍 종료하는거
		if (flag == false)
			Funct(n);
	}
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int s, w;
		cin >> s >> w;
		eggs[i] = make_pair(s, w);
	}

	Funct(0);
	cout << maxCnt;

	return 0;
}

 

문제에서 준 조건대로 백트래킹 이용해서 풀면 된다.

 

맨 오른쪽 계란에 도달하면 현재까지 깨진 계란의 개수를 카운트 하고, maxCount 에 반영한 후 빠져나오도록 했다.

 

맨 오른쪽 계란에 도달하지 않았으면 계속 조건대로 하면 된다. 현재 계란이 깨졌는지 확인하고 깨졌다면 다음 계란을 집어든다. 만약 깨지지 않았다면 현재 계란으로 다른 계란을 친다. 다른 계란을 치고 나서는 현재 들고 있었던 계란의 다음 계란을 들어야 함.

 

만약 더이상 칠 계란이 없으면 그냥 종료해야 하니까 flag 변수를 이용했다. flag 값으로 판단 한 후 Funct(n) 을 호출했다.