16987. 계란으로 계란치기

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

import java.util.Scanner;
 
// 16986 인싸들의 가위바위보 문제와 마찬가지로 dfs를 통한 완전탐색으로 해결했다.
// 처음 문제를 접했을 때 이걸 어떻게 해결하지 했다가 N이 최대 8이라는 것을 보고 바로 접근!
 
public class Main {
    static int N;
    static int eggCount=0;
    static class Egg{
        int weight;
        int dur;
        Egg(){
            weight=0;
            dur=0;
        }
        Egg(int d, int w){
            dur=d;
            weight=w;
        }
    }
    static void dfs(int turn, boolean[] isOk, int c, Egg[] eggs) {
    // 주의할 점은 계란을 들었다면 깨지지 않은 계란이 존재하는 한
    // 아무것도 치지 않고 다시 내려놓을 수 없다는 것이다.
    // 그래서 tempFlag를 통해 더이상 칠 계란이 없다면 바로 종료조건을 넣어주는 방법을 사용했다.
        if (turn == N) {
            eggCount = Math.max(c, eggCount);
            return;
        }    
        if (isOk[turn]) {
            dfs(turn + 1, isOk, c, eggs); // 계란이 이미 깨져있다면 다음으로 넘어감
        }
        else {
            boolean tempFlag = true;
            for (int i = 0; i < N; i++) {
                if (!isOk[i]) tempFlag = false; // 칠 수 있는 계란이 있다면 false
                if (!isOk[i]&&i!=turn) { // 계란이 깨져있지 않고 같은 계란이 아니라면
                    eggs[i].dur -= eggs[turn].weight;
                    eggs[turn].dur -= eggs[i].weight;
                    int tempCount = 0;
                    if (eggs[turn].dur <= 0) {
                        isOk[turn] = true;
                        tempCount++;
                    }
                    if (eggs[i].dur <= 0) {
                        isOk[i] = true;
                        tempCount++;
                    }
                    dfs(turn + 1, isOk, c+tempCount, eggs); // 쳐보고 넘긴 다음 원래대로 돌린다.
                    if (eggs[turn].dur <= 0) {
                        isOk[turn] = false;
                    }
                    if (eggs[i].dur <= 0) {
                        isOk[i] = false;
                    }
                    eggs[turn].dur += eggs[i].weight;
                    eggs[i].dur += eggs[turn].weight;
                }
            }
            if(!tempFlag) dfs(N, isOk, c, eggs); // 칠 수 있는 계란이 없다는 뜻이므로 바로 종료시킵니다.
        }
    }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        N=scan.nextInt();
        Egg eggs[]=new Egg[10];
        for(int i=0;i<N;i++) {
            int d=scan.nextInt();
            int w=scan.nextInt();
            eggs[i]=new Egg(d,w);
        }
        boolean isOk[]=new boolean[10];
        dfs(0, isOk, 0, eggs);
        System.out.println(eggCount);
    }
}