[BOJ/Java] 16987. 계란으로 계란치기

[BOJ/Java] 16987. 계란으로 계란치기

16987번: 계란으로 계란치기

---

풀이

package edu.ssafy.im.BOJ.Gold.G5.No16987;

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

public class Main {
    int n, ans; // 계란의 수와 최대 깰 수 있는 계란의 개수를 저장할 변수
    int[] durability, weight; // 각 계란의 내구도와 무게를 저장할 배열
    boolean[] isBroken, visited; // 각 계란의 깨진 여부와 방문 여부를 저장할 배열

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine()); // 계란의 수 입력 받음
        durability = new int[n]; // 내구도 배열 초기화
        weight = new int[n]; // 무게 배열 초기화
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            durability[i] = Integer.parseInt(st.nextToken()); // 내구도 입력 받음
            weight[i] = Integer.parseInt(st.nextToken()); // 무게 입력 받음
        }

        sol(0, 0); // 깰 수 있는 최대 계란 개수 구하는 메서드 호출

        sb.append(ans); // 결과를 StringBuilder에 추가

        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close();
    }

    private void sol(int idx, int cnt) {
        // basis part
        // 모든 계란을 다 확인한 경우
        if (idx == n) {
            ans = Math.max(ans, cnt); // 최대 깰 수 있는 계란 개수 갱신
            return;
        }

        // 손에든 계란이 깨졌거나 모든 계란이 깨진 경우
        if (durability[idx] <= 0 || cnt == n - 1) {
            sol(idx + 1, cnt); // 다음 계란으로 넘어감
            return;
        }

        // inductive part
        int tmp = cnt; // 현재 깰 수 있는 계란 개수 임시 저장
        for (int i = 0; i < n; i++) {
            if (i == idx) continue; // 본인인 경우 넘어감
            if (durability[i] <= 0) continue; // 이미 깨진 경우 넘어감

            // 깨기
            durability[i] -= weight[idx]; // 상대 계란의 내구도를 자신의 무게만큼 감소시킴
            durability[idx] -= weight[i]; // 자신의 내구도를 상대 계란의 무게만큼 감소시킴

            // 깨진 경우
            if (durability[idx] <= 0) cnt++; // 자신이 깨졌으면 깰 수 있는 계란 개수 증가
            if (durability[i] <= 0) cnt++; // 상대 계란이 깨졌으면 깰 수 있는 계란 개수 증가

            // 다음 계란으로 넘어감
            sol(idx + 1, cnt);

            // 깨진 거 복구
            durability[i] += weight[idx]; // 상대 계란의 내구도 복구
            durability[idx] += weight[i]; // 자신의 내구도 복구
            cnt = tmp; // 깰 수 있는 계란 개수 복구
        }
    }
}