백준 Q16987 계란으로 계란치기

문제가 뭐가 이렇게 긴지 모르겠지만 요약하자면 이거다.

1. 맨 왼쪽 계란부터 깨질 때까지 다른 계란을 친다.
2. 손에 든 계란이 깨졌다면 바로 오른쪽 계란을 든다.
3. 더 이상 깰 수 있는 계란이 없을 때까지 반복

위의 경우의 수들 중에 계란을 가장 많이 깰 수 있는 조합이 무엇인지 찾는 백트래킹 문제다.

로직 설계

1. 가장 왼쪽부터 깨지지 않은 계란을 선택한다.
2. 옆의 계란들을 백트래킹을 이용해 이렇게 저렇게 다 부셔본다.
3. 탈출조건은 맨 오른쪽의 계란을 집었을 때.

// eggMayo 클래스
class eggMayo {
        int durability;
        int weight;
        public eggMayo(int durability, int weight){
            this.durability = durability;
            this.weight = weight;
        }
}

private static void dfs(int current, int count){
    if(current == eggMayoList.size()){
        answer = Math.max(answer, count);
        return;
    }
    if(eggMayoList.get(current).durability<=0 || count == eggMayoList.size()-1){
         dfs(current+1, count);
         return;
    }
    int bfCount = count;
    for(int i=0; i<eggMayoList.size(); i++){
        if(i == current) continue;
            if(eggMayoList.get(i).durability<=0) continue;

            eggMayoList.get(current).durability -= eggMayoList.get(i).weight;
            eggMayoList.get(i).durability -= eggMayoList.get(current).weight;
            if(eggMayoList.get(current).durability <= 0) count++;
            if(eggMayoList.get(i).durability <= 0) count++;
            dfs(current+1, count);
            eggMayoList.get(current).durability += eggMayoList.get(i).weight;
            eggMayoList.get(i).durability += eggMayoList.get(current).weight;
            count = bfCount;
        }
    }

코드를 복사해두고 보니 변수명을 너무 길게 지어서 복잡해보이긴 하지만..
위의 로직대로 집어든 계란을 기준으로 다른 계란을 쳤을때 집어든 계란의 무게만큼 내리친 계란의 내구도를 서로 깎고 내구도가 0 이하로 떨어지게 되면 count를 올려준 방식으로 깨진 계란의 수를 구했다.