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

1. 문제

www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

2. 접근방법

N이 8뿐이 안되니

모든 경우의 수에 대해서 백트레킹으로 다 쳐보면 되는 문제

최악 7의 8제곱이 되겠다.

 

다만 계란을 부술 수 있는 최대 수인 N개의 경우를 찾으면 더 이상 찾아볼 필요가 없으니

모든 재귀를 종료시켜도 된다.

 

다만 현재 쥔 계란이 부서져있더라도 다음 계란으로 넘어가고

더 이상 칠 계란이 없더라도 다음 계란으로 넘어가야 한다.에 유의하자

3. 자바 코드

package Silver;

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

public class P16987계란으로계란치기 {
	static Point egg[];
	static int N, cnt, max;
	static boolean flag = false;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		egg = new Point[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			egg[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		dfs(0);
		System.out.println(max);

	}

	static void dfs(int idx) {
		if (idx == N) {
			max = Math.max(cnt, max);
			if (max == N)
				flag = true;
			return;
		}
		if (flag)
			return;
		if (egg[idx].x <= 0) {
			dfs(idx+1);
			return;
		}
		int broken = 0;
		for (int i = 0; i < N; i++) {
			if (i == idx) 
				continue;
			
			if (egg[i].x <= 0) {
				broken++;
				continue;
			}
			egg[idx].x -= egg[i].y;
			egg[i].x -= egg[idx].y;
			if (egg[idx].x <= 0)
				cnt++;

			if (egg[i].x <= 0)
				cnt++;

			dfs(idx + 1);

			if (egg[idx].x <= 0)
				cnt--;

			if (egg[i].x <= 0)
				cnt--;

			egg[idx].x += egg[i].y;
			egg[i].x += egg[idx].y;

		}
		if(broken == N-1) {
			dfs(idx+1);
		}

	}

}

4. 마치며

단순한 백트레킹 문제

백트레킹을 연습하기 좋은 문제였다.