(BOJ) 16987 계란으로 계란치기

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

소스 코드:

#include <iostream> #include <queue> #include <vector> #include <string> #include <string.h> #include <tuple> #include <algorithm> #define inf 987654321 using namespace std; typedef pair<int, int> P; int n,res; vector<P> v; void func(int cur,int cnt) { if (cur == n) { res = max(res, cnt); return; } if (v[cur].first<=0) return func(cur + 1, cnt);   // 현재 쥔 계란이 깨졌으면 다음 계란으로 넘어감 for (int i = 0; i < n; i++) { if (cur==i||v[i].first<=0) continue;  // 깰 계란이 현재 쥐고 있는 계란이거나 깨진 계란이면 패스 v[cur].first -= v[i].second; v[i].first -= v[cur].second;  // 부딪친 계란들은 내구력 감소 int t = 0; if (v[cur].first<= 0) {   // 쥐고 있는 계란이 깨지면 t++; } if (v[i].first<=0) {   // 부딪힌 계란이 깨지면 t++; } func(cur + 1, cnt + t);    v[cur].first += v[i].second;  // 초기화 v[i].first += v[cur].second;    } res = max(res, cnt); } int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; v.push_back({ a,b }); } func(0, 0); cout << res<<'\n'; return 0; }