[백준/Java] 16987번 계란으로 계란치기

-Code

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

public class BOJ16987 {
    static class Egg {
        int hp, weight;

        public Egg(int hp, int weight) {
            this.hp = hp;
            this.weight = weight;
        }
    }
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));

        int eggCnt = Integer.parseInt(br.readLine());
        // 계란 정보 셋팅
        Egg[] eggs = new Egg[eggCnt];
        for (int i = 0; i < eggCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int eggHp = Integer.parseInt(st.nextToken());
            int eggWeight = Integer.parseInt(st.nextToken());
            eggs[i] = new Egg(eggHp, eggWeight);
        }
        // 최대 부서진 계란 수 구하기
        breakEgg(0, eggs, eggCnt);
        // 최대값 출력
        System.out.println(answer);
    }

    private static void breakEgg(int now, Egg[] eggs, int eggCnt) {
        // 맨 오른쪽인 경우 최대값 계산
        if (now == eggCnt) {
            int cnt = 0;
            for (Egg egg : eggs) {
                cnt += egg.hp <= 0 ? 1 : 0;
            }
            answer = Math.max(answer, cnt);
            return;
        }
        // 현재 계란이 깨져있는 경우 다음 계란으로 이동
        if (eggs[now].hp <= 0) {
            breakEgg(now + 1, eggs, eggCnt);
            return;
        }
        // 계란끼리 부딛히기
        boolean noHit = true;
        for (int next = 0; next < eggCnt; next++) {
            if (next == now || eggs[next].hp <= 0) {
                continue;
            }
            // 백트랙킹
            eggs[now].hp -= eggs[next].weight;
            eggs[next].hp -= eggs[now].weight;
            breakEgg(now + 1, eggs, eggCnt);
            eggs[now].hp += eggs[next].weight;
            eggs[next].hp += eggs[now].weight;
            noHit = false;
        }
        // 계란이 다 깨져있는 경우 결과 계산
        if (noHit) {
            breakEgg(eggCnt, eggs, eggCnt);
        }
    }
}

처음에는 기본 DFS 로직을 짜고 visited로 계란이 깨진 경우를 계산하려 했는데 문제를 현재 들고 있는 계란을 들고 깨질 때까지 치는 것으로 이해해서 잘못 로직을 짰고, 문제가 코드가 길어져서 관리가 되지 않았습니다.

그래서 문제의 설명을 잘못 이해한 부분을 다시 다른 설명 등을 보고 바로 잡고 부분은 저장된 eggs의 hp를 통해 구해서 계산하는 방법을 사용해 보라는 힌트를 보고 해결했습니다. 하지만 이후 2가지 추가적인 문제가 생겼는데 현재 계란이 깨진 경우 다음으로 안 넘긴 것과 부딪힐 계란이 없는 경우 바로 계산 로직에 보내야 하는 것을 빼먹어서 문제가 생겼고 이 것들을 인지한 뒤 다시 풀어 해결했습니다.