백준 - 계란으로계란치기

문제 설명

계란에 대해 왼쪽부터 차례로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨는 문제

계란으로 계란을 치면서 가장 많이 깨뜨릴 수 있는 경우의 수를 구하는 문제이다.

계란을 하나를 잡고 계란을 친다. 그런데 중간에 손에든 계란이 깨졌거나 깨지지 않는 계란이 없으면 넘어간다.이후 손에 든 계란을 자리에 놓고 다음 계란을 들고 다시 다른 계란들을 깨뜨린다

주의사항

다른 계란을 깨뜨릴때 항상 오른쪽에만 있는 계란을 깨드리지 않아도 된다!

계란이 안깨져 있으면 모두 쳐보는 것이다!

풀이

public static void hit(int cnt) {
		if (n <= cnt) {
			long count = Arrays.stream(eggs).map(egg -> egg[0])
				.filter(durability -> durability <= 0)
				.count();
			answer = Math.max(answer, (int)count);
			return;
		}
		// 이미 깨져있으면 다른 계란을 선택해야 함.
		if (eggs[cnt][0] <= 0) {
			hit(cnt + 1);
		} else {
			boolean isRunnable = false; // 현재 cnt계란으로 칠수 있는 계란이 있는지
			for (int i = 0; i < n; i++) {
				if (i == cnt || eggs[i][0] < 0) {
					continue;
				}

				isRunnable = true;

				eggs[cnt][0] -= eggs[i][1];
				eggs[i][0] -= eggs[cnt][1];
				hit(cnt + 1);
				eggs[cnt][0] += eggs[i][1];
				eggs[i][0] += eggs[cnt][1];
			}

			// 현재 손에 쥐고 있는 계란으로 깨뜨릴게 더 없다면 다음 거를 집어서 다시 순차적으로 깨본다.
			if (!isRunnable) {
				hit(cnt + 1);
			}
		}

	}