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

 

 

[문제 바로가기]

1. 유형

브루트포스

DFS

백트래킹

 

2. 풀이

DFS를 쓰는 문제였습니다.

처음에 한글 이해하는게 조금 힘들었습니다.

2-1. 설계

 

 

2-2. 코드 풀이

3. 코드

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

public class Main {
	static int N, answer;
	static int arr[][];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		arr = new int[N][2];
		answer = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = stoi(st.nextToken());
			int b = stoi(st.nextToken());
			arr[i][0] = a;
			arr[i][1] = b;
		}
		per(0, 0);
		System.out.println(answer);
	}

	static void per(int level, int sum) {
		if(level==N) return;
		
		for (int i = 0; i < N; i++) {
			if(i == level || arr[i][0]<=0) continue;
			if(arr[level][0]<=0) {
				per(level+1, sum);
				return;
			}
			arr[level][0] -= arr[i][1];
			arr[i][0] -= arr[level][1];
			int cnt = 0;
			if (arr[level][0] <= 0)
				cnt++;
			if (arr[i][0] <= 0)
				cnt++;
			answer = Math.max(answer, sum+cnt);
			per(level + 1, sum + cnt);
			arr[level][0] += arr[i][1];
			arr[i][0] += arr[level][1];
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}