[백준] code.plus(브루트 포스 Part 2,JAVA)16987번, 계란으로 계란치기

문제 링크

16987번: 계란으로 계란치기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 계란에는 무게와 내구도가 존재합니다.

2. 계란끼리 부딪치면 내구도가 상대 계란의 무게만큼 감소합니다.

3. 계란을 순서대로 집어서 다른 계란과 부딪치게 합니다.

4. 계란을 부딪치는 모든 경우에서 깨지는 계란의 개수의 최대값을 결과로 출력합니다.

5. 계란의 내구도가 0이하가 되면 깨진다고 표현합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 순차적으로 계란을 부딪치는 모든 경우를 탐색합니다.

 

3. 모든 경우 탐색 후 계란이 깨지는 최대값을 결과로 출력합니다.

 

계란 부딪치기.

 

문제 설명에서 나와있는 그대로입니다.

 

계란1(내구도 : 30, 무게 : 20)

계란2(내구도 : 15, 무게 : 29)

 

계란1과 계란2가 부딪치기 진행

 

계란1 : 30 - 29 = 1

계란2 : 15 - 20 = -5

결과적으로 계란2만 깨집니다.

 

계란을 부딪쳐서 얻는 경우는 4가지입니다.

1. 계란1과 계란2가 모두 깨지는 경우

2. 계란1만 깨지는 경우

3. 계란2만 깨지는 경우

4. 둘 다 깨지지 않는 경우

 

예제입력 2.

 

1. 입력되는 정보들을 저장합니다.

 

N = 3

계란 1(내구도 : 1, 무게 : 100)

계란 2(내구도 : 8, 무게 : 5)

계란 3(내구도 : 3, 무게 : 5)

 

2. 순차적으로 계란을 부딪치는 모든 경우를 탐색합니다.

 

계란1과 계란2 부딪치기

계란1 : 1 - 5 = -4

계란2 : 8 - 100 = -92

 

계란2는 깨졌기 때문에 넘어가기

계란3은 부딪치려는 계란이 존재하기 않기 때문에 넘어가기

 

깨진 계란은 : 2개

 

계란1과 계란3 부딪치기

계란1 : 1 - 5 = -4

계란3 : 3 - 100 = -97

 

계란2는 부딪치려는 계란이 존재하기 않기 때문에 넘어가기

계란3은 깨졌기 때문에 넘어가기

 

깨진 계란은 : 2개

 

 

3. 모든 경우 탐색 후 계란이 깨지는 최대값을 결과로 출력합니다.

 

계란을 깨지는 최대값 2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 계란의 정보를 띄어쓰기 기준 나누었습니다.
• search을 이용해서 순차적으로 계란이 부딪치는 모든 경우를 탐색합니다.
• 모든 경우 탐색 후 얻을 수 있는 계란이 깨지는 최대값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 계란끼리 부딪치는 4가지 경우에 따라 탐색합니다.
• search함수는 탐색이 종료되었을 때 계란이 깨진 최대값을 비교합니다.

 

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

public class Main {
    //계란의 정보 관련 클래스
    static class egg{
        int S, W;
        public egg(int s, int w) {
            S = s;
            W = w;
        }
    }
    static int N, answer = -1;
    static boolean[] breaks;	//계란 깨지는 경우 확인
    static egg[] e;		//계란 정보 관련 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        e = new egg[N];
        breaks = new boolean[N];
        //입력되는 계란 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int S = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            e[i] = new egg(S,W);
        }
        search(0, 0);		//계란 부딪치는 모든 경우 탐색
        bw.write(answer + "");	//계란 깨지는 최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //순차적으로 계란이 부딪쳐서 깨지는 모든 경우 탐색
    static void search(int depth, int value){
        //모든 경우 종료되거나 계란이 N-1개 깨진 경우
        if(depth==N || value==N-1){
            answer = Math.max(answer, value);
            return;
        }
        //기준이 되는 계란이 깨진 경우
        if(breaks[depth]){
            search(depth+1, value);
            return;
        }
        //기준이 되는 계란이 깨지지 않은 경우 부딪치기 진행
        for(int i=0;i<N;i++){
            if(breaks[i] || i == depth)	//상대 계란이 깨지거나 자신인 경우
                continue;

            e[depth].S -= e[i].W;
            e[i].S -= e[depth].W;
            //부딪힌 계란 모두 깨지는 경우
            if(e[depth].S <= 0 && e[i].S <= 0){
                breaks[depth] = true;
                breaks[i] = true;
                search(depth+1, value+2);
                breaks[depth] =false;
                breaks[i] = false;
            }else if(e[i].S <= 0){		//상대 계란만 깨지는 경우
                breaks[i] = true;
                search(depth+1, value+1);
                breaks[i] = false;
            }else if(e[depth].S <= 0){	//기준 계란만 깨지는 경우
                breaks[depth] = true;
                search(depth+1, value+1);
                breaks[depth] = false;
            }else{		//둘 다 깨지지 않는 경우
                search(depth+1, value);
            }
            e[depth].S += e[i].W;
            e[i].S += e[depth].W;
        }
    }
}