백준 16987번: 계란으로 계란치기 [백트래킹][재귀][브루트포스] -Java

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

16987번: 계란으로 계란치기

 

다 좋았는데, 아래 조건을 놓쳤어서 헤맸었다.

 

1. 손에 든 계란으로 다른 계란은 한 번만 칠 수 있다.

 

문제가 길수록 아주 잘 읽어야한다는 것을 또 깨달았다..

 

계란을 하나 손에 들고 0~N번째 다른 계란을 다 쳐보는게 아니라

하나밖에 못친다는 것.

 

예제1의 내용을 보면 다음과 같다.

3
8 5 //1번 계란
1 100 //2번 계란
3 5 //3번 계란

 

답은 3이다.

치는 과정은,

(1) 1번 계란으로  3번 계란을 쳐서 3번 계란 깨트리기

(2) 2번 계란으로 1번 계란을 쳐서 1번,2번 계란 모두 깨트리기

 

가 되는 것이다.

나는 이부분에서 1번 계란이 3번쳤다가 2번쳐서 끝낸다고 생각했었다 ㅠ

 

 

<Java 코드>

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

public class Main {

	public static int N, ans = 0;
	public static boolean visit[];

	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		Egg[] list = new Egg[N];
		visit = new boolean[N];

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

		fun(0, list);

		System.out.println(ans);
	}

	public static void fun(int myidx, Egg[] list) {
		// 종료조건 : 맨 오른쪽 계란인가?
		if (myidx == N) {
			int sum = 0;
			for (int i = 0; i < list.length; i++) {
				if (list[i].durability <= 0)
					sum++;
			}
			ans = Math.max(sum, ans);
			return;
		}
		
//		System.out.println("+"+myidx);
		if (list[myidx].durability > 0) { // 현재 손에 든 계란이 깨지지 않았는지?

			boolean nextExisits = false;
			for (int i = 0; i < N; i++) {

				if(myidx == i ) //손에 든 계란과 같은 idx인가?
					continue;
				if (list[i].durability <= 0) // 다른 계란이 깨져있는가?
					continue;

				nextExisits = true;
				// 부딪혀보기
				list[myidx].durability -= list[i].weight;
				list[i].durability -= list[myidx].weight;
				fun(myidx+1, list);

				// 원복
				list[myidx].durability += list[i].weight;
				list[i].durability += list[myidx].weight;

			}
			
			if(!nextExisits) //칠 계란이 없었다면 다음걸 쥐자
				fun(myidx+1, list);
		} else {
			fun(myidx + 1, list);
		}
	}

}

class Egg {
	int durability;
	int weight;

	public Egg(int d, int w) {
		this.durability = d;
		this.weight = w;
	}
}