[백준] 16987 - 계란으로 계란치기

[문제링크]

16987번: 계란으로 계란치기

 

0. 내구도/데미지 값을 고려해서 가능한 많은 계란을 깨는 문제

 

1. 재귀를 사용해서 모든 경우의 수를 진행한다

• 현재 계란이 깨지지 않았다면, 이걸로 다른 깨지지 않은 계란을 친다
• 깨졌다면, 그냥 넘어간다
• 다음번 계란으로 넘어가서 반복한다
• 모든 계란에 대해 시도했다면, 종료하고 깬 계란 수를 관리한다
• 계산 편의, 효율을 위해 깨진 계란의 수를 인자로 관리한다

 

2. 위 과정에서 나온 값들 중 최댓값을 저장, 출력

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int cnt = pint(br.readLine());
		int[][]egg = new int[cnt][2];
		
		for(int i=0; i<cnt; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int S = pint(st.nextToken());
			int W = pint(st.nextToken());
			egg[i][0]=S;
			egg[i][1]=W;
		}
		
		System.out.println(rec(egg, 0, 0));
	}
	
	static int rec(int[][]egg, int curEgg, int breaked) {
		if(curEgg>=egg.length) {
			return breaked;
		}
		
		if(egg[curEgg][0]<=0) {
			return rec(egg, curEgg+1, breaked);
		}
		
		int ans=breaked;
		for(int i=0; i<egg.length; i++) {
			if(egg[i][0]<=0 || i==curEgg)continue;
			
			egg[curEgg][0]-=egg[i][1];
			egg[i][0]-=egg[curEgg][1];
			
			int tmpBreaked=0;
			tmpBreaked+= egg[curEgg][0]<=0?1:0;
			tmpBreaked+= egg[i][0]<=0?1:0;
			
			ans=Math.max(ans, rec(egg,curEgg+1,breaked+tmpBreaked));
			
			egg[curEgg][0]+=egg[i][1];
			egg[i][0]+=egg[curEgg][1];
		}
		return ans;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면