문제
문제
각 계란에는 내구도와 무게가 정해져있다.
계란으로 계란을 치게 되면 각 계란의 내구도는 상대 계란의 무게만큼 깎이게 된다.
그리고 내구도가 0 이하가 되는 순간 계란은 깨지게 된다.
예를 들어 계란 1의 내구도가 7, 무게가 5이고 계란 2의 내구도가 3, 무게가 4라고 해보자.
계란 1으로 계란 2를 치게 되면 계란 1의 내구도는 4만큼 감소해 3이 되고 계란 2의 내구도는 5만큼 감소해 -2가 된다.
충돌 결과 계란 1은 아직 깨지지 않았고 계란 2는 깨졌다.
규칙에 따라 깰 수 있는 계란의 최댓값을 구하라.
규칙
- 가장 왼쪽의 계란을 든다.
- 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다.
2-1. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.
2-2. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.- 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다.
3-1. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.
입력
첫째 줄에 계란의 수를 나타내는 N(1 ≤ N ≤ 8)가 주어진다.
그 다음 N개의 줄에는 계란의 내구도와 무게에 대한 정보가 주어진다.
i+1번째 줄에는 왼쪽에서 i번째에 위치한 계란의 내구도 Si(1 ≤ Si ≤ 300)와 무게 Wi(1 ≤ Wi ≤ 300)가 한 칸의 빈칸을 사이에 두고 주어진다.
출력
첫째 줄에 인범이가 깰 수 있는 계란의 최대 개수를 출력한다.
입출력 예시
입력
3 -> 계란의 수 N(1 ≤ N ≤ 8)
8 5 -> 각 계란의 내구도Si(1 ≤ Si ≤ 300) 무게 Wi(1 ≤ Wi ≤ 300)
1 100
3 5출력
3
접근법
아이디어
- 가장 왼쪽 계란(루트) 부터 시작, 어떤 계란을 치느냐에 따라 결과가 달라짐 -> 트리 형태
- 상태 변화
- 계란끼리 부딪히면 양 쪽 다 내구도 깎임
- 상태 복구
- 다음 시나리오 확인 위해 깎인 내구도 원래대로 돌려놓음
- 가지치기
- 손에 든 계란이 깨졌다
- 칠 계란이 없다(다른 모든 계란이 깨져 있다)
변수
static int n; //계란 수
static int[][] eggsInfo; //계란 내구도 무게 정보
static int maxCnt; //깰 수 있는 최대 계란 수
static int[][] nowEgg; //계란 상태 두는 임시 변수코드
전체 코드
import java.util.Scanner;
public class BOJ_16987 {
static int n; //계란 수
static int[][] eggsInfo; //계란 내구도 무게 정보
static int maxCnt; //깰 수 있는 최대 계란 수
static int[][] nowEgg; //계란 상태 두는 임시 변수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt(); //계란 수
eggsInfo = new int[n][2]; //[][0] : 내구도 [][1] : 무게
nowEgg = new int[n][2];
maxCnt=0;
for(int i = 0;i<n;i++) {
nowEgg[i][0] = eggsInfo[i][0]=sc.nextInt();
nowEgg[i][1] = eggsInfo[i][1]=sc.nextInt();
}
eggCnt(0);
System.out.println(maxCnt);
}
static void eggCnt(int idx) {
//종료조건
if(idx == n) {
int tempCnt = 0;
for(int i = 0;i<n;i++) {
if(nowEgg[i][0]<=0) {
tempCnt++;
}
}
maxCnt=Math.max(tempCnt, maxCnt);
return;
}
//가지치기
//손에 든 계란이 깨졌으면 다음 계란으로
if(nowEgg[idx][0]<=0) {
eggCnt(idx+1);
return;
}
//재귀파트
//나를 제외한 다른 누군가 하나를 선택해서 무조건 치고 넘어감
//칠 수 있는 계란이 있는지 확인
boolean flag= false;
for(int i = 0; i<n;i++) {
if(i==idx)continue; //자기 자신은 못 침
if(nowEgg[i][0]<=0)continue; //이미 깨진 계란 못 깸
//여기로 왔으면 계란 깰 수 있다는 얘기
flag = true;
nowEgg[i][0]-=eggsInfo[idx][1];
nowEgg[idx][0]-=eggsInfo[i][1];
eggCnt(idx+1);
//상태복구
nowEgg[i][0]+=eggsInfo[idx][1];
nowEgg[idx][0]+=eggsInfo[i][1];
}
if(!flag){
eggCnt(idx+1);
}
}
}
상세 코드
선택
- 손에 쥔 계란으로 어떤 계란을 칠지 선택
- 가능한 선택지로 파고듦(DFS)
for(int i = 0; i<n;i++) {
...
}재귀 종료 조건
- 0번부터 탐색 끝났을 경우
if(idx == n) {
int tempCnt = 0;
for(int i = 0;i<n;i++) {
if(nowEgg[i][0]<=0) {
tempCnt++;
}
}
maxCnt=Math.max(tempCnt, maxCnt);
return;
}가지치기
- 손에 든 계란이 깨졌으면 넘어감
if(nowEgg[idx][0] <= 0) {
eggCnt(idx+1);
return;
}- 칠 대상이 깨졌으면 후보에서 제외
if(nowEgg[i][0] <= 0) continue;- 칠 수 있는 계란이 없으면 다음 단계로 넘어감
if(!flag){
eggCnt(idx+1);
}상태 변경
- 선택한 계란을 쳐서 상태 변경
nowEgg[i][0] -= eggsInfo[idx][1];
nowEgg[idx][0] -= eggsInfo[i][1];재귀 파트
eggCnt(idx+1);상태 복구
- 다음 경우의 수 위해 원상복구
nowEgg[i][0] += eggsInfo[idx][1];
nowEgg[idx][0] += eggsInfo[i][1];리뷰
- 해당 문제는 백트래킹 중 의사결정 및 최적화 에 해당
- 매 단계에서 어떤 계란을 칠지 결정하고, 그 선택들의 결과 중 최대값 찾기 때문
- 선택 후 다시 되돌리는 구조 = 백트래킹
- 해당 문제에서 조건에 따라 계산을 건너뛰어도 된다 = 백트래킹
- 조건 탐색 매우 중요
- 백트래킹의 핵심은 상태 원상복구
