[백준] 16987: 계란으로 계란치기 - JAVA

27 Apr 2024 in Algorithm on 브루트포스 알고리즘

https://www.acmicpc.net/problem/16987

풀이

계란마다 내구도, 무게가 주어진다.

계란끼리 부딪혔을 때 내구도는 상대 계란의 무게만큼 깎이는데, 내구도가 0이하가 되면 계란이 깨진다.

계란을 최대 몇개 깰 수 있는지 구해야 한다.

dfs를 통해 1번 계란 부터 진행했다.

idx번 계란을 어떤 계란과 부딪혔을 때 계란들의 내구도와 깨진 개수를 갱신해 idx+1번으로 넘어가 진행한다.

반복문을 통해 해당 계란이 여러 번호의 계란과 부딪히는 것을 시뮬레이션해볼 수 있도록 부딪힌 후에 결과를 초기화 해주는 과정이 필요했다.

---

메모리: 15708KB

시간: 232ms

언어: Java 11

코드

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

public class Main {
    static int n, answer;
    static int[] durability, weight;

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

        durability = new int[n];
        weight = new int[n];

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

        answer = 0;
        dfs(0, 0);

        System.out.println(answer);
    }

    private static void dfs(int idx, int cnt) {
        if (idx == n) {
            answer = Math.max(cnt, answer);
            return;
        }

        if (durability[idx] <= 0 || cnt == n - 1) {
            dfs(idx + 1, cnt);
            return;
        }

        int tmp = cnt;
        for (int i = 0; i < n; i++) {
            if (i == idx || durability[i] <= 0) {
                continue;
            }

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

            if (durability[i] <= 0) {
                tmp++;
            }
            if (durability[idx] <= 0) {
                tmp++;
            }

            dfs(idx + 1, tmp);

            durability[i] += weight[idx];
            durability[idx] += weight[i];
            tmp = cnt;
        }
    }

}