[백준][Java] 16987번 : 계란으로 계란치기
[문제 링크]
https://www.acmicpc.net/problem/16987
문제 설명
각 계란은 내구도와 무게를 가지고 있다.
계란으로 계란을 치면, 각 계란의 내구도는 상대 계란의 무게만큼 깎인다.
내구도가 0 이하면 계란이 깨진다.
ex) 계란 1의 내구도 7 무게 5, 계란 2의 내구도 3 무게 4
두 개란을 치면, 계란 1의 내구도는 7-4=3, 계란 2의 내구도는 3-5=-2 으로 계란 2가 깨진다.
일렬로 놓인 계란을 왼쪽부터 차례로 들어서 아래와 같은 규칙으로 한번씩만 쳐서 계란을 깨뜨린다.
1. 가장 왼쪽 계란을 든다.
2. 현재 들고있는 계란으로 깨지지 않은 다른 계란을 하나 친다.
이 때, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 넘어간다.
3. 현재 들고있는 계란을 내려놓고, 가장 최근에 든 계란의 바로 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다.
이 때, 가장 최근에 든 계란이 가장 오른쪽일 경우, 계란치기를 종료한다.
최대한 많이 깨뜨릴 수 있는 계란의 개수를 구한다.
문제 풀이
나의 풀이
- 제일 왼쪽 계란부터 순서대로 모든 경우를 탐색하는 방식
- 1차원 배열 broken을 통해서 해당 계란이 깨졌는지 안깨졌는지를 표시한다.
- 손에 든 계란이 깨졌거나, 깨지지 않은 다른 계란이 없을 경우 현재 손에 든 계란을 놓고 오른쪽 계란을 들어서 계란치기 과정을 수행한다. → eggBreak(hand + 1, cnt)
- 손에 든 계란과 다른 계란을 쳐서
- 각 계란의 내구도를 갱신
- 두 계란이 깨졌는지 확인해서 cnt 증가, broken 배열 갱신
- 재귀 호출로 현재 손에 든 계란의 오른쪽에 위치한 계란으로 이동 후 과정 수행
- 재귀 호출이 끝나면, 내구도, cnt, broken 배열 원상복구
전체코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int n, max = 0;
static int[][] eggs;
static boolean[] broken = new boolean[8];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine()); //계란의 수
eggs = new int[n][2];
//계란의 내구도와 무게 입력받기(왼 -> 오)
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
eggs[i][0] = Integer.parseInt(st.nextToken()); //내구도
eggs[i][1] = Integer.parseInt(st.nextToken()); //무게
}
eggBreak(0, 0);
System.out.println(max);
}
/**
* @param hand 손에 들고 있는 계란의 인덱스
* @param cnt 깬 계란의 개수
*/
public static void eggBreak(int hand, int cnt) {
//종료 - 가장 최근의 든 계란이 가장 오른쪽 계란일 경우
if (hand == n) {
max = Math.max(max, cnt);
return;
}
//손에 든 계란이 깨졌거나, 깨지지 않은 다른 계란이 없는 경우
if (broken[hand] || cnt == n - 1) {
eggBreak(hand + 1, cnt);
return;
}
int temp = cnt;
for (int i = 0; i < n; i++) {
if (hand == i) {
continue;
}
//깨지지 않은 다른 계란일 경우 계란 치기 실행
if (!broken[i]) {
hitEgg(hand, i); //두 계란을 치기
if (eggs[hand][0] <= 0) {
cnt++;
broken[hand] = true;
}
if (eggs[i][0] <= 0) {
cnt++;
broken[i] = true;
}
eggBreak(hand + 1, cnt);
restoreEgg(hand, i);//원래대로
cnt = temp;
}
}
}
//두 계란 치기
private static void hitEgg(int hand, int i) {
//계란의 내구도 -= 상대 계란의 무게
eggs[hand][0] -= eggs[i][1];
eggs[i][0] -= eggs[hand][1];
}
private static void restoreEgg(int hand, int i) {
eggs[hand][0] += eggs[i][1];
eggs[i][0] += eggs[hand][1];
broken[hand] = false;
broken[i] = false;
}
}
다른 풀이
1. broken 배열
위의 풀이에서 보면 계란의 깨짐여부를 나타내는 broken 배열이 있는데, 생각해보면 이는 굳이 필요하지 않다.
eggs 배열에서 계란의 내구도가 0 이하인 경우 계란이 깨진 상태이다. 그렇기 때문에 (계란의 내구도) <= 0 으로 계란의 깨짐여부를 를 판단할 수 있다.
2. temp 변수
for문을 시작하기 전에 현재 cnt의 값을 temp에 임시로 저장해두었다. 이는 재귀가 끝나고서 cnt값을 원상복구할 때 사용하기 위해서이다.
하지만 아래와 같이 재귀호출 시에 삼항연산자로 각 계란이 깨졌는지 안깨졌는지를 따져서 cnt를 증가시키면 temp는 없어도 된다.(계란이 깨진 경우 1, 깨지지 않은 경우 0)
3. flag 변수
위의 풀이에서 보면 '깨지지 않은 다른 계란이 없을 경우' 손에 든 계란을 놓고 오른쪽 계란을 들어서 계란치기 과정을 수행하도록 했다. → eggBreak(hand + 1, cnt)
여기에서는 flag 라는 변수를 사용해서 현재 손에 든 계란으로 계란치기를 한 번이라도 수행했는지를 표시한다.
수행한 경우 true, 수행하지 못한 경우 false
계란치기를 한번이라도 수행하지 못한 경우 → 깨지지 않은 다른 계란이 없다는 의미 이다.
eggBreak(hand + 1, cnt + (eggs[hand][0] <= 0 ? 1 : 0) + (eggs[i][0] <= 0 ? 1 : 0));다른 풀이 코드
public static void eggBreak(int hand, int cnt) {
//종료 - 가장 최근의 든 계란이 가장 오른쪽 계란일 경우
if (hand == n) {
max = Math.max(max, cnt);
return;
}
if (eggs[hand][0] <= 0) { //손에 든 계란이 깨진 경우 -> 내려놓고 다음 계란을 든다
eggBreak(hand + 1, cnt);
} else { //손에 든 계란이 깨지지 않은 경우 -> 계란치기 실행
boolean flag = false; //계란치기를 한번이라도 했는지 안했는지
for (int i = 0; i < n; i++) {
if (hand == i || eggs[i][0] <= 0) { //
continue;
}
flag = true;
eggs[hand][0] -= eggs[i][1];
eggs[i][0] -= eggs[hand][1];
eggBreak(hand + 1, cnt + (eggs[hand][0] <= 0 ? 1 : 0) + (eggs[i][0] <= 0 ? 1 : 0));
eggs[hand][0] += eggs[i][1];
eggs[i][0] += eggs[hand][1];
}
if (!flag) { //깨지지 않은 계란이 없어서 한 번도 치지 못한 경우
eggBreak(hand + 1, cnt);
}
}
}[참고]
https://www.youtube.com/watch?v=QgG1hIkrZME