Algorithm

백준 16987 : 계란으로 계란치기

쿠케캬캬 2022. 2. 5. 00:30
반응형

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

 

16987번: 계란으로 계란치기

원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱

www.acmicpc.net

 

 

왼쪽 계란부터 아직 안깨진 계란과 부딪치게 하면서 최대로 깨뜨릴 수 있는 계란의 수를 구해주었습니다.

#include <iostream>
#include <algorithm>
#define MAX 8
using namespace std;

int n, s[MAX], w[MAX], ans = 0;

void breakEggs(int idx, int cnt) {
	ans = max(ans, cnt);
	if (idx == n) return;
	if (s[idx] <= 0) breakEggs(idx + 1, cnt);
	else {
		for (int i = 0; i < n; i++) {
			if (s[i] <= 0 || idx == i) continue;
			s[idx] -= w[i];
			s[i] -= w[idx];
			breakEggs(idx + 1, cnt + (s[idx] <= 0) + (s[i] <= 0));
			s[i] += w[idx];
			s[idx] += w[i];
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

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

	breakEggs(0, 0);
	cout << ans;
}
반응형