16987 계란으로 계란치기

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

16987번: 계란으로 계란치기

문제의 조건이 복잡하게 되어 있어 헷갈렸던 문제였다. 조건을 살펴보면 상태를 기억하기 위한 재귀 호출이 필요하다는걸 눈치챌 수 있는데, 계란을 치고 내구도가 감소된 상태에서 다음 계란을 칠 지 판단하는 것, 내구도가 0이하인 계란은 더 이상 치지 않고 다음 계란으로 넘어가는 조건을 통해 판단했다.

N의 크기가 작기 때문에 브루트포스로 전부 탐색해도 무리가 없다.

import java.io.*;
import java.util.*;

public class Main {
  public static int N, answer = 0;
  public static int[] W, S;
  public static void recur(int idx){
    if(idx == N){
      int cnt = 0;
      for(int i = 0; i < N; i++){
        if(S[i] <= 0) cnt++;
      }
      answer = Math.max(answer, cnt);
      return;
    }
    if(S[idx] <= 0){
      recur(idx + 1);
    }
    //현재 계란의 내구도가 0보다 크다면
    else{
      boolean isBroken = false;
      //왼쪽부터 순서대로 탐색
      for(int i = 0; i < N; i++){
        if(idx == i || S[i] <= 0)
          continue;
        //부딪힌 계란이라면, 상태를 기억하기 위해 재귀 호출
        isBroken = true;
        S[i] -= W[idx];
        S[idx] -= W[i];
        recur(idx + 1);
        S[i] += W[idx];
        S[idx] += W[i];
      }
      //부딪힐 계란이 없다면 오른쪽으로 넘어감
      if(isBroken == false)
        recur(idx + 1);
    }
  }
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    W = new int[N]; S = new int[N];
    for(int i = 0; i < N; i++){
      st = new StringTokenizer(br.readLine());
      S[i] = Integer.parseInt(st.nextToken());
      W[i] = Integer.parseInt(st.nextToken());
    }
    recur(0);
    System.out.println(answer);
  }
}