문제

BOJ 16987: 계란으로 계란치기 https://www.acmicpc.net/problem/16987

풀이

• 계란을 깨는데 조건
  • 계란에는 내구도(dura)와 무게(weight)가 있다.
  • 계란을 계란끼리 치면 계란의 내구도(dura)는 다른 계란의 무게(weight)만큼 깎인다.
  • 계란의 내구도(dura)가 0 이하가 되면 깨진다.
• 계란을 가장 왼쪽부터 차례로 손에 들고 다른 계란들을 랜덤으로 선택한다.
  • 만약 손에 든 계란이 깨져있거나 다른 계란들 전부가 깨져있다면 아무일도 하지 않고 넘어간다.
  • 랜덤으로 선택된 계란 중 깨지지 않은 계란과 부딪히게 한다.
  • 최근에 손에 든 계란의 바로 오른쪽 계란을 선택하여 손으로 들고 위의 과정을 반복한다.
• 왼쪽부터 차례로 든 계란으로 한 번 씩만 다른 계란과 부딪히게 하여 최대한 많은 계란을 깨도록 한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N;
	static int[] dura;
	static int[] weight;
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		dura = new int[N];
		weight = new int[N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			dura[i] = Integer.parseInt(st.nextToken()); // 계란의 내구도
			weight[i] = Integer.parseInt(st.nextToken()); // 계란의 무게
		}
		
		bt(0, 0); // 0번째 계란부터 시작 , 이 땐 깨진 계란 0개
		
		System.out.println(max);
	}
	
	static void bt(int idx, int cnt) {
		// 마지막 계란까지 다 들어봤으면 종료
		if(idx == N) {
			// 최댓값 갱신
			max = Math.max(max, cnt);
			return;
		}
		// 손으로 든 계란이 이미 깨졌거나 모든 계란이 이미 다 깨져 있다면
		if(dura[idx] <= 0 || cnt == N-1) {
			// 다음 계란을 들어 봄
			bt(idx + 1, cnt);
			return;
		}
		// 다른 계란들과 모두 부딪혀봄
		int nCnt = cnt;
		for(int i=0; i<N; i++) {
			// 손으로 들고 있는 계란과 부딪히려고 하는 계란이 같은 계란이라면 통과
			if(i == idx) continue;
			// 부딪혀 보려고 하는 계란이 이미 깨져있다면 통과
			if(dura[i] <= 0) continue;
			// 계란끼리 부딪혀봄 (현재 손에 들고 있는 계란의 인덱스, 부딪혀보려는 타겟 계란 인덱스)
			hitEgg(idx, i);
			// 부딪혀 봤는데 손에 든 계란이 깨지면 cnt++
			if(dura[idx] <= 0) {
				cnt++;
			}
			// 부딪혀 봤는데 타겟이 된 계란이 깨지면 cnt++
			if(dura[i] <= 0) {
				cnt++;
			}
			// 재귀 호출 -> 다음 계란 들어 봄
			bt(idx + 1, cnt);
			// for문의 다음 i를 위해 값을 원상복구 해 줌
			recoveryEgg(idx, i);
			cnt = nCnt;
		}
	}
	
	// 계란끼리 부딪혀보는 메소드
	static void hitEgg(int handEgg, int targetEgg) {
		dura[targetEgg] -= weight[handEgg];
		dura[handEgg] -= weight[targetEgg];
	}
	
	// 다시 원상복구 하는 메소드
	static void recoveryEgg(int handEgg, int targetEgg) {
		dura[targetEgg] += weight[handEgg];
		dura[handEgg] += weight[targetEgg];		
	}
	
}

정리

• 다른 백트래킹 문제에선 가능한 조합을 모두 만들어 놓고 종료 조건 안에서 마무리 연산을 해주는 경우가 많았다.
• 이번 문제에선 종료조건이 아닌 재귀호출을 하기위한 for문 안에서 연산을 하여 해결하는 문제였다.
• 재귀만을 사용하여 해결하는 것이 아니라 유망한 조건만 추려서 재귀 호출을 사용하는 문제였다.