[백준] 계란으로 계란 치기 java

1. 문제에 대하여 📦

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

(1) 조건 분석 📊

1. 계란이 횡으로 존재하고, 순차적으로 하나씩 손에 쥔다.
2. 손에 쥔 계란과 행에 아직 존재하는 계란 중 하나를 부딪힌다. 그러면 각각의 내구도가 서로의 무게만큼 깎인다.
3. 내구도가 0 이하로 내려가면 깨진다.
4. 손에 쥘 차례가 된 계란이 이미 깨져 있으면 넘어간다.
5. 최대한 계란을 많이 깼을 때 그 갯수를 구하라.

2. 코드가 나오기까지 🛠️

KEY WORD: 백트래킹

이걸 백트래킹으로 풀지 않으면 중복순열로 풀어야 한다. 왜냐하면, 손에 쥔 계란마다 때릴 계란을 고를텐데, 손에 쥔 계란마다 때릴 계란은 무조건 하나여야 하지만, 맞는 계란은 복수의 계란에게서 맞을 수 있기 때문이다.

아무리 $N \leq 8$ 이라지만, 중복순열은 시간복잡도 상 위험하다. 따라서 백트래킹으로 풀어야 한다.

백트래킹이 줄여주는 경우의 수는 다음과 같다.

1. 손에 쥘 계란이 깨져있으면 계산 과정 없이 다음 계란으로 넘어간다.
2. 손에 쥘 계란과 깨질 계란이 같으면 넘어간다.
3. 때릴 계란이 이미 깨져 있으면 넘어간다.
4. 모든 계란을 확인한 기저 조건이 아니더라도, 현재 손에 쥔 계란 제외 모든 계란이 깨져있으면 깨진 계란 최대값을 갱신하고 탈출한다.

이 경우의 수들만 줄여도 획기적으로 준다. 다음은 중복순열로 풀었을 때와 백트래킹으로 풀었을 때의 성능 차이이다.

중복 순열 풀이

백트래킹 풀이

지금까지 제일 중요한 것은 이해했으니, 이제 백트래킹에서 제일 실수하기 쉬운 것들만 조심하면 된다.

1. 이전 깊이로 복귀하기 전에 썼던 자료구조 값들 혹은 전역 변수 값을 쓰기 이전과 동일하게 되돌리기
2. 문제 조건의 분기 규칙 잘 지키기

(1) 시간복잡도 분석 ⏳

N <= 8 이고, 백트래킹으로 불필요한 경우의 수 계산을 피했기 때문에 괜찮을 것 같다.

3. 코드 🌐

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

public class Main {

    static class Egg {
        int hp;
        int w;

        public Egg(int hp, int w){
            this.hp = hp;
            this.w = w;
        }

        @Override
        public String toString() {
            return "체력:"+ this.hp + "\t 무게: " + this.w;
        }
    }
    static int N;
    static int ans = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        Egg [] eggs = new Egg[N];

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int hp = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            eggs[i] = new Egg(hp, weight);
        }

        recur(0, eggs, 0);
        System.out.println(ans);
    }

    public static void recur (int depth, Egg [] eggs, int cnt){
        if(depth == N) {
            ans = Math.max(ans,cnt);
            return;
        }
        // 이미 깨진 계란이거나, 이거 제외 모든 계란이 이미 다 깨진 상태라면 다음 계란으로 넘어간다.
        if(eggs[depth].hp <= 0 || cnt == N-1) {
            recur(depth+1, eggs, cnt);
            return;
        }
        for(int i = 0; i < N; i++){
            if(i == depth) continue;
            if(eggs[i].hp <= 0) continue;

            int new_cnt = cnt;
            eggs[i].hp -= eggs[depth].w;
            eggs[depth].hp -= eggs[i].w;

            if(eggs[i].hp <= 0) new_cnt++;
            if(eggs[depth].hp <= 0) new_cnt++;

            recur(depth+1, eggs, new_cnt);
            eggs[i].hp += eggs[depth].w;
            eggs[depth].hp += eggs[i].w;
        }
    }
}

4. 트러블 슈팅 or 배운 점📝

1. 손에 쥘 계란이 이미 깨져있으면, 다음 계란으로 넘어가지 않고 이전 재귀로 복귀한 점

   • 지문을 제대로 읽어야 한다.

2. 기저 조건을 최대 깊이로만 계산한 점

   • 문제에서 제공하는 예제 2번을 보면, 깊이가 기저 조건까지 가지 않아도 모든 계란이 깨져서, 재귀가 기저조건까지 가지 못했다. 따라서 최대값 갱신이 안되었는데, 이에 대한 예외처리가 필요하다.