[JAVA] 백준 (골드5) 16987번 계란으로 계란치기

링크

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

---

입력 예제

3
8 5
1 100
3 5

---

출력 예제

3

---

풀이

모든 계란을 순서대로 사용하여 나머지 계란과 부딪히고, 깨진 계란이 최대가 됐을 때의 개수를 구해야 한다.

입력값이 다음과 같이 주어져, 3개의 계란이 존재할 때

3
8 5
1 100
3 5

1번째 계란부터 사용한다면, 2번째 계란과 부딪히거나, 3번째 계란과 부딪히는 경우가 있다.

만약 2번째 계란을 부딪힌다면, 계란의 상태를 업데이트하고, 다음 계란인 2번째 계란을 사용하여야 한다.

1: -92
2:  -4
3:   5

하지만 2번째 계란은 이미 깨져있기 때문에, 3번째 계란으로 넘어간다. 하지만 깨진 계란밖에 없고, 마지막 계란이기 때문에 탐색을 종료한다. 그리고 상태를 복귀하여 1번째 계란이 3번째 계란을 부딪히는 경우를 계산한다. 이렇게 3번째 계란을 부딪히는 경우도 끝까지 계산한 뒤 탐색을 종료한다. 그리고 마지막 계란까지 사용한 경우에 재귀를 종료한다.

이 문제를 해결하기 위해서는 모든 가능한 경우의 수를 탐색하면서, 불필요한 경로는 가지치기를 통해 이전 상태로 되돌아가는 백트래킹으로 구현해야 한다.

우선 계란의 내구도와 무게를 저장할 Egg 클래스를 생성한다.

static class Egg {
    int durability;
    int weight;
    
    public Egg(int durability, int weight) {
        this.durability = durability;
        this.weight = weight;
    }
    
    boolean isCracked() {
        return this.durability <= 0;
    }
}

그리고 백트래킹을 진행할 재귀 함수롤 생성하는데, 우선 마지막 계란까지 사용할 경우 재귀를 종료시키고, 깨진 계란의 개수를 구하고, 최댓값을 갱신한다.

if (now == N) {  //마지막 계란까지 사용하면 리턴
    int count = 0;
    for (Egg egg : eggs) {
        if (egg.isCracked()) {
            count++;
        }
    }
    max = Math.max(max, count);
    return;
}

그리고 현재 들고 있는 계란이 깨졌을 경우 스킵해야 하므로 다음 재귀를 호출하고 재귀를 종료한다.

Egg curEgg = eggs[now];
if (curEgg.isCracked()) {  //현재 계란이 깨진 경우 재귀 호출
    recur(now + 1);
    return;
}

현재 계란이 깨지지 않았을 경우, 모든 계란에 대해 탐색을 진행한다. 이때 타겟 계란이 깨진 경우는 스킵하고, 계란의 상태를 갱신한다. 그리고 그 상태로 재귀를 호출한다. 이 재귀와는 별도로 백트래킹으로 구현하기 위해 상태를 원복시킨다.

boolean hasTarget = false;
for (int i = 0; i < N; i++) {
    Egg target = eggs[i];
    //타겟 계란이 깨진 경우 스킵
    if (i == now || target.isCracked()) {
        continue;
    }
    hasTarget = true;
    target.durability -= curEgg.weight;
    curEgg.durability -= target.weight;
    recur(now + 1);
    target.durability += curEgg.weight;
    curEgg.durability += target.weight;
}

그리고 탐색을 하면서 깰 수 있는 계란이 없을 경우가 있을 수도 있는데 그때도 역시 다음 계란을 사용하기 위해 재귀를 호출한다.

if (!hasTarget) {  //깰 수 있는 계란이 없을 경우 재귀 호출
    recur(now + 1);
}

전체 코드

//백준
public class Main {

    static Egg[] eggs;
    static int N, max;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        recur(0);
        System.out.println(max);
    }

    static void recur(int now) {
        if (now == N) {  //마지막 계란까지 사용하면 리턴
            int count = 0;
            for (Egg egg : eggs) {
                if (egg.isCracked()) {
                    count++;
                }
            }
            max = Math.max(max, count);
            return;
        }

        Egg curEgg = eggs[now];
        if (curEgg.isCracked()) {  //현재 계란이 깨진 경우 재귀 호출
            recur(now + 1);
            return;
        }

        boolean hasTarget = false;
        for (int i = 0; i < N; i++) {
            Egg target = eggs[i];
            //타겟 계란이 깨진 경우 스킵
            if (i == now || target.isCracked()) {
                continue;
            }
            hasTarget = true;

            target.durability -= curEgg.weight;
            curEgg.durability -= target.weight;
            recur(now + 1);
            target.durability += curEgg.weight;
            curEgg.durability += target.weight;
        }

        if (!hasTarget) {  //깰 수 있는 계란이 없을 경우 재귀 호출
            recur(now + 1);
        }
    }

    static class Egg {
        int durability;
        int weight;

        public Egg(int durability, int weight) {
            this.durability = durability;
            this.weight = weight;
        }

        boolean isCracked() {
            return this.durability <= 0;
        }
    }
}