[Baekjoon] 16987_계란으로 계란치기

Gold V

문제(출처: https://www.acmicpc.net/problem/16987)

---

< 계란으로 계란치기 >

 

문제 풀이 

 

계란 하나로 다른 계란을 깰 수 있는 모든 경우의 수를 확인한다.

 

 my solution (Java)

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

public class _16987_ { // 계란으로 계란치기
	static Egg arr[];
	static boolean visited[];
	static int cnt, result;

	static class Egg {
		private int d;
		private int w;

		public Egg(int d, int w) {
			this.d = d;
			this.w = w;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		arr = new Egg[n];
		visited = new boolean[n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			arr[i] = new Egg(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}

		result = 0;
		cnt = 0;

		search(0);

		System.out.println(result);
	}

	private static void search(int idx) {
		for (int i = 0; i < arr.length; i++) {
			if (idx == i) {
				continue;
			}
			if (!visited[i]) {
				arr[idx].d -= arr[i].w;
				arr[i].d -= arr[idx].w;

				if (arr[i].d <= 0) {
					cnt += 1;
					visited[i] = true;
				}
				if (arr[idx].d <= 0) {
					cnt += 1;
					visited[idx] = true;
				}

				if(result < cnt ) {
					result= cnt;
				}

				int temp=idx+1;
				while(temp<arr.length && visited[temp]) {
					temp++;
				}
				if(temp < arr.length) {
					search(temp);
				}
				arr[idx].d += arr[i].w;
				arr[i].d += arr[idx].w;

				if (arr[i].d-arr[idx].w <=0 && arr[i].d > 0) {
					cnt -= 1;
					visited[i] = false;
				}
				if (arr[idx].d-arr[i].w <=0 && arr[idx].d > 0) {
					cnt -= 1;
					visited[idx] = false;
				}
			}
		}
	}
}

변수)
Egg : 내구도(d), 무게(w)를 변수로 가지는 클래스
n : 계란의 수
arr : 계란 정보
visited : 계란 깨진 여부
result : 깰 수 있는 계란의 최대 개수
cnt : 완전 탐색을 하는 동안 깰 수 있는 계란 수

 

계란의 수를 입력받는다. 계란의 수만큼 계란의 내구도와 무게를 입력받아 arr 배열에 계란의 정보를 저장한다. search 함수를 호출해서 깰 수 있는 계란의 최대 개수를 구해 출력한다.

 

search(idx)

계란을 전체 탐색하면서 다음 과정을 수행한다.

1)  idx==i 인 경우 자기 자신을 칠 수 없으므로 넘어간다.

2) 아직 깨지지 않은 계란이라면 친다

3) 서로 쳐서 깨진 계란이 있다면 cnt+1, 깨진 처리를 한다. 

4) 깰 수 있는 계란의 최대 개수를 업데이트한다.

5) 현재 idx에서 오른쪽 계란을 살펴보며 아직 깨지지 않은 계란을 선택해 search 함수를 호출한다.

6) 완전탐색을 위해 3) 과정을 되돌린다. 

---

---