[BOJ]16987 - 계란으로 계란치기 (S1)

문제 링크

16987-계란으로 계란치기

입력

첫째 줄에 계란의 수를 나타내는 N(1 ≤ N ≤ 8)가 주어진다.
그 다음 N개의 줄에는 계란의 내구도와 무게에 대한 정보가 주어진다.
i+1번째 줄에는 왼쪽에서 i번째에 위치한 계란의 내구도 Si(1 ≤ Si ≤ 300)와 무게 Wi(1 ≤ Wi ≤ 300)가 한 칸의 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 인범이가 깰 수 있는 계란의 최대 개수를 출력한다.

문제 풀이

주석으로 해결 방법 표기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, max = Integer.MIN_VALUE;
    static int[] weight, dura;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

    static void dfs(int idx, int cnt) {
        // 마지막 계란까지 다 돈 경우
        if (idx == N) {
            max = Math.max(max, cnt);
            return;
        }

        // 계란을 집었는데 깨져있는 경우
        // 더 이상 꺨 계란이 없는 경우
        if (dura[idx] <= 0 || cnt == N - 1) {
            dfs(idx + 1, cnt);
            return;
        }

        int count = cnt;
        for (int i = 0; i < N; i++) {
            // 내가 들고 있는 계란과 부딪히려는 계란이 같은 경우
            if (i == idx) continue;
            // 부딪히려는 계란이 이미 깨진 경우
            if (dura[i] <= 0) continue;

            dura[i] -= weight[idx];
            dura[idx] -= weight[i];

            if (dura[idx] <= 0) cnt++;
            if (dura[i] <= 0) cnt++;
            dfs(idx + 1, cnt);

            // 다음 케이스에 사용해야하니깐 다시 복구
            dura[i] += weight[idx];
            dura[idx] += weight[i];
            cnt = count;

        }
    }
}