[G5] 백준 16987번 계란으로 계란치기 C++ 백트래킹

리뷰

 

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

계란끼리 부딪혀 최대한 많이 깰 수 있는 계란의 개수를 구하는 문제

 

 

전역 변수

• n : 계란의 개수를 저장할 변수
• ans : 깰 수 있는 최대 계란의 개수를 저장할 변수
• s : 계란의 내구도를 저장할 배열
• w : 계란의 무게를 저장할 배열

 

함수

1. bt

void bt(int level)

 

백트래킹을 통해 계란을 깨는 모든 경우를 체크하기 위한 함수

1. 매개 변수로 현재 재귀 단계 및 손에 든 계란의 번호를 나타낼 level을 전달 받는다.
2. 기저 조건으로 level이 n이 도달했을 경우 내구도가 0이하인 계란의 개수를 구해 max를 최신화 하고 리턴한다.
3. 두 번째 기저 조건으로 만약 현재 계란의 내구도가 0이하일 경우 다음 계란으로 재귀를 진행한 후 빠져나올때 리턴한다.
4. 변수 flag를 false인 상태로 초기화 하고, n개의 계란 정보를 순회해 준다.
5. 만약 현재 계란과 번호가 같으면 continue, 계란의 내구도가 이미 0이하일 경우 continue해준다.
6. 만약 계란을 칠 수 있다면 flag를 true로 변경해 준다.
7. 각 계란의 무게만큼 내구도를 깎아주고 재귀 단계를 높혀 재귀를 진행해 준다.
8. 재귀를 빠져나온 후에는 각 계란의 무게만큼 내구도를 다시 더해준다.
9. 탐색을 마치고 나서 flag가 여전히 false인 상태라면 재귀 단계를 높혀 재귀를 진행해 준다.

 

문제풀이

1. n값을 입력 받고, n개의 계란의 내구도와 무게를 각각 s, w배열에 입력 받아준다.
2. bt함수에 0을 전달하여 재귀 단계가 0일 때부터 백트래킹을 진행해 준다.
3. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. for문 내부에서 현재 계란의 내구도가 0이하인 경우 continue 처리해 주지 않아 값이 더 크게 나왔다.
2. 현재 계란의 내구도가 0이하일 경우 continue처리해 주니 정답을 맞게 되었다.

 

참고 사항

• 가지 치기로 두 번째 기저 조건에서 재귀수행 후 아래 for문을 진행하지 않기 위해 return을 했더니 4ms가 줄었다.
• N값이 작아 의미없는 가지치기가 된 것 같다.

 

정답 코드

#include<iostream>
using namespace std;

int n, ans;
int s[8], w[8];

void bt(int level) {
	if (level == n) {
		int cnt = 0;
		for (int i = 0; i < n; ++i) if (s[i] <= 0) cnt++;
		ans = max(ans, cnt);
		return;
	}
	if (s[level] <= 0) {
		bt(level + 1);
		return;
	}

	bool flag = 0;
	for (int i = 0; i < n; ++i) {
		if (i == level) continue;
		if (s[i] <= 0) continue;
		flag = 1;

		s[level] -= w[i];
		s[i] -= w[level];
		bt(level + 1);
		s[level] += w[i];
		s[i] += w[level];
	}

	if (!flag) bt(level + 1);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> s[i] >> w[i];
	bt(0);
	cout << ans;
}