[백준] 16987번: 계란으로 계란치기 (Java)

1. 문제설명

계란은 내구도와 무게에 대한 정보가 주어지고, 왼쪽부터 차례로 들어 한 번씩만 다른 계란 쳐 최대한 많은 계란을 깨는 문제이다. 계란의 내구도는 상대 계란으 무게만큼 깎이게 되고, 내구도가 0 이하가 되면 깨진다.

계란을 치는 과정:

1. 가장 왼쪽 계란을 든다.
2. 들고 있는 계란으로 다른 계란 중 하나를 친다. 만약 손에 든 계란이 깨졌거나 다른 모든 계란이 깨진 경우 넘어간다.
3. 최근에 든 계란의 오른쪽 계란을 들고 2번 과정을 반복한다. 가장 오른쪽 계란을 들게 되면 종료한다.

• 시간 제한: 2초
• 메모리 제한: 512MB

 

2. 접근 방식

참고: https://buly.kr/4bgWSet

• 계란의 내구도와 무게를 각각 다른 배열에 저장한다.
• 백트래킹을 사용하여 계란을 깨뜨리는 모든 경우의 수를 구한다.
  • 마지막 계란을 드는 경우 종료 (깨진 계란의 최댓값 찾음)
  • 손에 든 계란이 이미 깨졌거나, 이미 다른 모든 계란이 깨져있으면 넘어감 (다음 계란 들기)
  • for문을 사용해 다른 계란들과 모두 부딪혀봄
    • 손에 들고 있는 계란과 같은 계란이면 패스
    • 부딪히려는 계란이 이미 깨진 계란이면 패스
    • 부딪혔을 때 계란 깨지면 count 증가
    • 다음 계란(오른쪽)으로 재귀 호출
    • 재귀 호출 후 계란 원래대로 복구

 

3. 최종 코드

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

public class Main {
    static int n; // 계란 개수
    static int[] dur; // 내구도
    static int[] weight; // 무게
    static int maxCnt = Integer.MIN_VALUE; // 깨진 계란 최대 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dur = new int[n];
        weight = new int[n];

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            dur[i] = Integer.parseInt(st.nextToken());
            weight[i] = Integer.parseInt(st.nextToken());
        }

        backTrack(0, 0);
        System.out.println(maxCnt);
    }

    static void backTrack(int eggIdx, int cnt) {
        // 손에 드는 계란 인덱스, 깨진 계란 수를 파라미터로 받음

        // 마지막 계란을 드는 경우 종료 (깨진 계란의 최댓값 찾음)
        if(eggIdx == n) {
            maxCnt = Math.max(maxCnt, cnt);
            return;
        }

        // 손에 든 계란이 이미 깨졌거나, 이미 다른 모든 계란이 깨져있으면 넘어감 (다음 계란 들기)
        if(dur[eggIdx] <= 0 || cnt == n-1) {
            backTrack(eggIdx+1, cnt);
            return;
        }

        int backCnt = cnt;
        // 다른 모든 계란과 부딪혀봄
        for(int i=0; i<n; i++) {
            // 손에 들고 있는 계란이면 패스
            if(i == eggIdx) continue;

            // 부딪히려는 계란이 이미 깨진 계란이면 패스
            if(dur[i] <= 0) continue;

            // 부딪혔을 때 계란 깨지면 cnt 증가
            dur[eggIdx] -= weight[i];
            dur[i] -= weight[eggIdx];
            if(dur[eggIdx] <= 0) cnt++;
            if(dur[i] <= 0) cnt++;

            // 다음 계란(오른쪽)으로 재귀 호출
            backTrack(eggIdx+1, cnt);

            // 계란 원래대로 복구
            dur[eggIdx] += weight[i];
            dur[i] += weight[eggIdx];
            cnt = backCnt;
        }
    }
}