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

문제

 

 

접근 방식

굉장히 오래 걸려서 푼 문제인데 풀고 나니 쓸데없는 곳에서

시간 낭비를 많이 한 문제 같다.

 

우선 계란끼리 서로 부딪혔을 때 내구도가 0 이하로 떨어진다면

해당 계란은 깨진 계란이라고 기록을 남겨주고 각 계란들의 내구도를 갱신해 준다.

 

계란의 내구도는 자신의 내구도 - 부딪힌 상대 계란의 무게로

계란 객체 배열이나 정수형 배열로 부딪힌 후의 내구도를 갱신해 주면 된다.

 

처음에는 가장 왼쪽에 있는, 즉 배열의 0번째 인덱스 (now)의 계란을 손에 쥐고

깨지지 않은 계란을 아무거나 하나 골라 둘을 부딪히게 한다.

 

그 후 계란을 모두 내려놓고 방금 집었던 계란의 오른쪽 한 칸 (now + 1)의 계란을 손에 쥐고

다시 깨지지 않은 계란을 아무거나 하나 골라 부딪히게 하는 것을 반복해 주면 된다.

 

이제 주의해야 할 부분이 있는데 만약 자신이 손에 쥔 계란이 깨진 계란이라면

오른쪽으로 한 칸씩 움직이면서 깨지지 않은 계란을 찾아야 한다.

 

재귀 함수의 기저조건은 문제에 나와 있는 것처럼

오른쪽으로 한 칸씩 움직이면서 모든 계란을 다 집었을 때로

now == n일 때를 기저조건으로 지정해주면 된다.

 

풀이

public class Main {

	private static int n;
	private static int max = 0;
	private static Egg[] eggs;
	private static boolean[] isBroken;

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

		n = Integer.parseInt(br.readLine());

		eggs = new Egg[n];
		isBroken = new boolean[n];

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

		eggToEgg(0, 0);

		System.out.println(max);
	}

	private static void eggToEgg(int now, int count) {
		if (now == n) {
			max = Math.max(max, count);
			return;
		}

		if (isBroken[now]) {
			eggToEgg(now + 1, count);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (!isBroken[i] && i != now) {
				Egg egg = eggs[now];
				Egg newEgg = eggs[i];

				egg.durability = egg.durability - newEgg.weight;
				newEgg.durability = newEgg.durability - egg.weight;

				if (egg.durability <= 0) {
					isBroken[now] = true;
					count++;
				}
				if (newEgg.durability <= 0) {
					isBroken[i] = true;
					count++;
				}

				eggToEgg(now + 1, count);

				egg.durability = egg.durability + newEgg.weight;
				newEgg.durability = newEgg.durability + egg.weight;

				if (isBroken[now]) count--;
				if (isBroken[i]) count--;

				isBroken[now] = false;
				isBroken[i] = false;
			}

			max = Math.max(count, max);
		}
	}

	private static class Egg {
		int durability;
		int weight;

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