[BOJ 16987] 계란으로 계란치기

 

16987번: 계란으로 계란치기

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

백트래킹으로 모든 경우를 탐색하여 푼다.

 

- 가장 왼쪽의 계란을 든다 --> dfs(0,0) // 시작점을 0으로 주어 맨 왼쪽부터 시작하도록 한다.

 

- 손에 들고 있는 계란으로 꺠지지 않은 다른 계란 중에서 하나를 친다.

   * 손에 든 계란이 꺠졌거나 --> 현재 들고 있는 계란의 내구도가 0이거나

   * 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다 --> 타겟 계란의 내구도가 0인 것을 계속 체크하여 넘어간다.

      - 이 경우를 확인하기 위해 boolean형의 check변수를 두어 칠 수 있는 계란이 하나도 없는 경우였다면 false,

      - 칠 수 있는 계란이 하나라도 있었다면 true 상태로 둔다.

 

- 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 종료한다

   * 시작점이 N과 동일한 경우 종료한다.

 

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

public class Main {

    static class Egg {
        int s,w; // s는 내구도, w는 무게

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

    static List<Egg> eggList = new ArrayList<Egg>();
    static int ans = 0;

    public static void main(String []args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        int s,w;
        String[] input;
        for (int i=0; i<n; i++) {
            input = br.readLine().split(" ");
            s = Integer.parseInt(input[0]);
            w = Integer.parseInt(input[1]);

            eggList.add(new Egg(s,w));
        }

        dfs(0,0);

        sb.append(ans);
        System.out.println(sb);

        wr.close();
        br.close();
    }

    private static void dfs(int start,int cnt) {

        if (start == eggList.size()) { // 기저조건 : 최근에 만진 계란이 가장 오른쪽
            ans = Math.max(ans,cnt);
            return;
        }

        boolean check = false;
        for (int i=0; i < eggList.size(); i++) {

            if (start == i) continue; // 시작점과 부시려는 계란이 같은 경우 continue

            int s1 = eggList.get(start).s; // 현재 계란의 내구도를 뽑는다
            int s2 = eggList.get(i).s; // 타겟 계란의 내구도를 뽑는다

            if (s1 <= 0) { // 내가 집은 계란이 부서져있는 계란인 경우 다음 단계로 가야하고 돌아와서는 아무것도 수행할 수 없음.
                dfs(start + 1, cnt);
                return;
            }
            if (s2 <= 0) continue;

            check= true; // 칠 수 있는 타겟 계란이 존재한다는 의미로 true로 변경

            int w1 = eggList.get(start).w;
            int w2 = eggList.get(i).w;

            eggList.get(start).s = s1 - w2; // 현재 내구도에서 타겟 계란의 무게만큼 뺀다
            eggList.get(i).s = s2 - w1; // 타겟 내구도에서 현재 계란의 무게만큼 뺀다

            int tempcount = 0;

            if (eggList.get(start).s <= 0) tempcount++;
            if (eggList.get(i).s <= 0) tempcount++;

            dfs(start + 1, cnt + tempcount);

            eggList.get(start).s = s1; // 원래대로 원상복귀
            eggList.get(i).s = s2; // 원래대로 원상복귀

        }

        if(!check) dfs(start + 1,cnt);
        // 칠 수 있는 계란, 즉 타겟 계란이 하나도 없었던 경우더라도 기저조건을 만나기 위해
        // 다음 계란을 만져보러 가야 한다.
    }

}