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

1. 문제

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

16987번: 계란으로 계란치기

 

 

2. 풀이 과정

손에 든 계란으로 어떤 계란을 칠 지에 따라 DFS탐색을 한다.

DFS가 끝나면 다른 길 탐색을 위해, 이전에 바꿔준 변수를 되돌려준다.

 

이때 주의할 점은 두 가지였다.

여기서 자기 자신은 깰 수 없다는 것과 손에 든 계란이 깨질 경우와 친 계란이 깨질 경우를 모두 고려해서 cnt를 증가시켜야 한다는 점이다.

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

public class Main {

    static int N, eggs[][], crackedCnt;

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

        N = Integer.parseInt(br.readLine());
        eggs = new int[N][2];

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

        simulation(0, 0);
        System.out.println(crackedCnt);
    }

    public static void simulation(int now, int cnt){
        if(cnt == N-1 || now == N){
            crackedCnt = Math.max(crackedCnt, cnt);
            return;
        }
        if(eggs[now][0] <= 0){//손에 든 계란이 깨졌을 때
            simulation(now + 1, cnt);
        }
        else{//손에 든 계란이 안 깨졌을 때
            for (int i=0; i<N; i++){
                if(i == now){
                    continue;
                }
                if(eggs[i][0] > 0) {
                    eggs[i][0] -= eggs[now][1];
                    eggs[now][0] -= eggs[i][1];
                    simulation(now + 1, cnt + (eggs[i][0] <= 0 ? 1 : 0) + (eggs[now][0] <= 0 ? 1 : 0));
                    eggs[now][0] += eggs[i][1];
                    eggs[i][0] += eggs[now][1];
                }
            }

        }

    }
}

 

 

결과