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

 

 

문제 출저

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

16987번: 계란으로 계란치기

 

 

 

 

문제 풀이

계랸아 n개 주어진다. 각각의 계란은 내구도와 무게를 가지고 있다. 계란끼리 부딫이면 서로의 무게 만큼 내구도가 감소한다. 내구도가 0 이하가 되면 깨진 것으로 한다. 왼쪽부터 계란을 들어 깨지지 않는 계란과 부딫힌다. 이 때 깨진 계란은 들지 않는다. 계란끼리 부딫혔을 때, 계란이 최대한 많이 깨진 갯수를 구하는게 이 문제의 요구사항이다.

 

 

백트래킹으로 풀었습니다.

분기를 나누어 손에 든 계란의 내구도가 0 이하여서 깨진 경우 그대로 넘어갔습니다. 

만약 내구도가 있다면 for문으로 하나씩 깨뜨린 다음 진행하여 모든 경우의 수를 탐색했습니다.

이 때, boolean flag를 만들어 한 번도 부딫힐 수 없는 경우를 확인했습니다. 한 번도 못 부딫힐 경우 다음으로 넘어가게 했습니다.

 

 

 

 

소스 코드

package baekjoon.backjoon9.day28;

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

/*
계란으로 계란치기
https://www.acmicpc.net/problem/16987

내구도와 무게가 주어진다.
계란끼리 부딫히면 무게 만큼 내구도가 감소한다.
 */
public class B16987 {

    static int n;
    static int[][] eggs;
    static int answer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        eggs = new int[n][2];

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            eggs[i][0] = Integer.parseInt(st.nextToken()); // 내구도
            eggs[i][1] = Integer.parseInt(st.nextToken()); // 무게
        }

        answer = 0;

        dfs(0);

        System.out.println(answer);

    }

    public static void dfs(int stage) {

        if(stage == n) {
            int result = 0;
            for(int i = 0; i < n; i++) {
                if(eggs[i][0] <= 0) {
                    result++;
                }
            }
            answer = Math.max(answer, result);
            return;
        }

        int durability = eggs[stage][0];
        int weight = eggs[stage][1];

        // 이미 깨진 계란은 넘어간다.
        if(durability <= 0) {
            dfs(stage+1);
        }
        else {

            boolean flag = false;

            for(int i = 0; i < n; i++) {
                if(i == stage) {
                    continue;
                }

                if(eggs[i][0] > 0) {
                    flag = true;

                    eggs[i][0] -= weight;
                    eggs[stage][0] -= eggs[i][1];
                    dfs(stage+1);
                    eggs[i][0] += weight;
                    eggs[stage][0] += eggs[i][1];
                }
            }

            if(flag == false) {
                dfs(stage + 1);
            }
        }
    }
}