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

1. 문제 풀이

 백트래킹 문제입니다. 계란의 내구도 정보를 백트래킹의 조건 중 하나로 사용하면 쉽게 풀 수 있습니다. 예를 들어 i번째 계란으로 j번째 계란을 친다고 한다면 s[i]는 w[j]만큼 감소시키고, s[j]는 w[i]만큼 감소시키면서 s[i]나 s[j]가 0 이하가 되면 계란이 깨진 것으로 간주할 수 있습니다. 따라서 상태 공간 트리에서 깨진 계란과 아직 깨지지 않은 계란을 판별할 수 있어 문제 풀이가 가능합니다.

 

2. 코드

// Authored by : chjh2129
#include <bits/stdc++.h>

using namespace std;

int n;
int s[10], w[10]; // s[i] : i-th 계란 내구도, w[i] : i-th 계란 무게

int ans; // 깰 수 있는 계란의 최대 개수

/*
  k-th 계란을 손에 들고 있음.
*/
int broken; // 현재 깨진 계란의 개수
void solve(int k){
  // 1st base condition
  // 최근에 손에 든 계란이 가장 오른쪽에 위치한 계란임
  if(k == n){ 
    ans = max(ans, broken);
    return;
  }

  // 2nd base condition
  // 손에 들고 있는 계란이 깨져있거나, 모든 계란이 부셔져 있음.
  if(s[k] <= 0 || broken == n-1){
    solve(k+1);
    return;
  }

  for(int i = 0; i < n; i++){
    if(k == i || s[i] <= 0) continue; // 깨려는 계란이 자기자신이거나 이미 깨져있으면 넘어감
    s[k] -= w[i];
    s[i] -= w[k];
    if(s[k] <= 0) broken++;
    if(s[i] <= 0) broken++;
    solve(k+1);
    if(s[k] <= 0) broken--;
    if(s[i] <= 0) broken--;
    s[k] += w[i];
    s[i] += w[k];
  }
}

int main(){
  cin.tie(nullptr)->sync_with_stdio(false);

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

  // solve
  solve(0);

  // output
  cout << ans;
}

 

3. 제출 결과