BOJ_16987_계란으로 계란치기

1

구분: 브루트포스, 백트레킹

언어: Java

전략

1. DFS를 이용하여  칠 순서대로 계란을 찾는다

2. 손에 든 계란이 깨져있다면 pass

3. 깨려는 계란이 손에 든 계란이라면 pass

4. 계란을 치고, 깨진 계란이 있다면 깨진 것들 개수를 더한다. 재귀를 부른다 

5. 다시 원상 복구를 한다(DFS의 특징)

6. 맨 오른쪽 계란을 잡고 깬다면 이제 그만

7. 매번 최대값을 갱신

---

2. 코드

package algorithm.boj;
import java.util.Scanner;

public class BOJ_16987 {
	static class Egg{
		int power;
		int weight;
		boolean state;//true는 아직 안깨진것, false는 꺠진것
		Egg(int power, int weight, boolean state){
			this.power = power;
			this.weight = weight;
			this.state = state;
		}
	}
	static int n, max;
	static Egg[] eggs;
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		max = Integer.MIN_VALUE;
		eggs = new Egg[n];
			
        //계란을 입력받는다
		for(int i = 0; i<n; i++) {
			eggs[i] = new Egg(scanner.nextInt(), scanner.nextInt(), true);
		}
		dfs(0,0);
		System.out.println(max);
		
	}//main
	
	
	//현재 손에 든 계란(now), 지금까지 깨진 게란 수 
	private static void dfs(int now, int cnt) {
		//최대값 갱신
		max = Math.max(cnt, max);
		
		if(now == n) {
			return;
		}

		//손에 든 계란이 깨져 있다면 그냥 넘어가 
		if(!eggs[now].state) {
			dfs(now+1, cnt);
			return;
		}
		
		
		for(int i = 0; i<n; i++) {
			int temp = 0;
			//내 자신이면 넘어가 
			if(now == i)
				continue;
			//이미 깨진거면 지나가 
			if(!eggs[i].state)
				continue;
			
			//계란 깨기
			eggs[now].power-=eggs[i].weight;
			eggs[i].power-=eggs[now].weight;
			
			//깨진것들 상태 바꾸고, 개수 증가
			if(eggs[now].power<=0) {
				eggs[now].state = false;
				temp++;
			}
			if(eggs[i].power<=0) {
				eggs[i].state = false;
				temp++;
			}
			
			//다음 칸으로 이동, 꺠진개수도 갱신
			dfs(now+1, cnt+temp);
			
			
			//원상 복구 - 상태 복구, 내구성 복구  
			if(eggs[now].power<=0) {
				eggs[now].state = true;
			}
			if(eggs[i].power<=0) {
				eggs[i].state = true;
			}
			eggs[i].power+=eggs[now].weight;
			eggs[now].power+=eggs[i].weight;
		
		}
		
	}//dfs
	

}

---

3

• 처음에는 순열을 구했다 - 시간 초과 발생(8!)
• DFS의 원상 복구를 안했다 - 처음에는 값만 복구함, 상태도 복구 해주어야 한다. 
• 오랜만에 문제 푸니 많이 낯설다! 꾸준히 공부하자