링크

16987 계란으로 계란치기

문제

풀이

문제가 상당히 긴데 계란으로 계란을 치는 것이다.
계란으로 계란을 치게 되면 각 계란의 내구도는 상대 계란의 무게만큼 깎인다.
계란을 치는 방법은

1. 가장 왼쪽의 계란을 든다.
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

이 과정을 반복한다.

백트래킹으로 풀었고 다른 백트래킹 문제보다 조건이 많아서 조금 까다롭다(?)

코드

import java.awt.desktop.PreferencesEvent;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.Buffer;
import java.sql.Array;
import java.util.*;

class Egg{
    int state;
    int weight;

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

    @Override
    public String toString() {
        return "Egg{" +
                "state=" + state +
                ", weight=" + weight +
                '}';
    }
}

public class Main {

    public static List<Egg> list = new ArrayList<>();
    public static int answer = 0;

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

        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list.add(new Egg(a, b));
        }

        dfs(0, 0);
        System.out.println(answer);
        
    }

    public static void dfs(int dept, int breakCount){
        answer = Math.max(answer, breakCount);
        if(dept == list.size()){
//            System.out.println("dept == list.size() return");
            return;
        }

        if(list.get(dept).state <= 0) {
//            System.out.println("dept = " + dept + " 잡은 계란 깨짐");
            dfs(dept+1, breakCount);
            return;
        }

        for(int i=0;i<list.size();i++){
            // dept는 현재 쥔 계란, cnt는 때릴 계란
            if(dept == i) continue;

            //현재 쥔 계란이 깨진 경우
            if(list.get(i).state <= 0) continue;

            Egg gripEgg = list.get(dept);
            Egg targetEgg = list.get(i);

//            System.out.println("------------------------------------");
//            System.out.println("dept = " + dept + " i = " + i);
//            System.out.println("변경 전");
//            System.out.println("current Egg = " + gripEgg);
//            System.out.println("target Egg = " + targetEgg);
//            for(Egg element : list){
//                System.out.println(element);
//            }

            list.set(dept, new Egg(gripEgg.state - targetEgg.weight, gripEgg.weight));
            list.set(i, new Egg(targetEgg.state - gripEgg.weight, targetEgg.weight));

            int breakEgg = 0;
            if(list.get(dept).state <= 0){
                breakEgg++;
            }

            if(list.get(i).state <= 0){
                breakEgg++;
            }

//            System.out.println("변경 후");
//            System.out.println("current Egg = " + list.get(dept));
//            System.out.println("target Egg = " + list.get(i));
//            for(Egg element : list){
//                System.out.println(element);
//            }

            dfs(dept+1, breakCount + breakEgg);

//            System.out.println("--------------------------------");
//            System.out.println("백트래킹 전");
//            for(Egg element : list){
//                System.out.println(element);
//            }

            list.set(dept, gripEgg);
            list.set(i, targetEgg);

//            System.out.println("백트래킹 후");
//            for(Egg element : list){
//                System.out.println(element);
//            }


        }

    }
}