계란으로 계란치기 [백준 16987][실버3][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

16987번: 계란으로 계란치기

1. 처음 해보는 DFS유형의 문제

2. EGG배열을 만들어서 내구도, 무게, 깨졌는지 여부, 최근 계란, 깨진 수 를 저장한다.

3. DFS를 돌면서 가장 왼쪽부터 계란을 깬다. 

4. 만약 손에 든 계란이 깨졌다면 다음 계란으로 넘어간다.

5. 다음 계란도 깨져있다면 그 다음 계란으로 넘어간다.

6. DFS를 돌고 난 후 다시 복구 해 준다(다음 케이스에서 사용해야 하므로)

 

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

class Egg{
	int hard, weight, current, cnt;
	boolean isbreak;
	public Egg(int hard, int weight, boolean isbreak,int current, int cnt) {
		this.hard = hard;
		this.weight = weight;
		this.isbreak = isbreak;
		this.current = current;
		this.cnt = cnt;
	}
}
public class 계란으로계란치기 {
	public static Egg[] eggs;
	public static int N,ans=Integer.MIN_VALUE;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
	
		eggs = new Egg[N];
		for (int i = 0; i < N; i++) {
			eggs[i] = new Egg(sc.nextInt(), sc.nextInt(),false,0,0);
		}
		
		dfs(0,0);
		if(ans == Integer.MIN_VALUE) System.out.println(0);
		else System.out.println(ans);
	}
	public static void dfs(int idx, int cnt) {
		//가장 오른쪽 계란에 도달
		if(idx == N) return;
		
		Egg egg = eggs[idx];
		if(egg.isbreak) {
			//계란이 깨졌으면 다음 계란으로 넘김
			dfs(idx+1, cnt);
			return;
		}
		for (int i = 0; i < N; i++) {
			int temp = 0;
			//같은 계란
			if(idx == i) continue;
			//깨진 계란
			if(eggs[i].isbreak) continue;
			
			//계란 계산
			egg.hard -= eggs[i].weight;
			eggs[i].hard -= egg.weight;
			
			if(egg.hard <= 0) {
				egg.isbreak = true;
				temp++;
			}
			if(eggs[i].hard <= 0) {
				eggs[i].isbreak = true;
				temp++;
			}
			//최대 갱신
			ans = Math.max(cnt + temp, ans);
			//dfs 시작
			dfs(idx + 1,cnt+temp);
			
			//원상복구
			if(egg.hard <= 0) {
				egg.isbreak = false;
			}
			if(eggs[i].hard <= 0) {
				eggs[i].isbreak = false;
			}
			
			egg.hard += eggs[i].weight;
			eggs[i].hard += egg.weight;
		}
	}
}