<Algorithm> 143. 계란으로 계란치기(BJO)

1. 16987번 계란으로 계란치기(BJO)

• 백트래킹 문제

• 이문제는 기본 백트래킹 문제지만 꼼꼼한 처리가 필요했다.

• 이미 쥔 달걀이 깨진 경우에 return을 안걸어서 문제가 잇었고 또 이미 다 깨진 경우에 대한 처리를 안해서 92 퍼센트에서 계속 틀렸다.

• 처리해야 될 부분을 따로 적어놓고 확실하게 처리해주어야 겠다.

import java.util.Scanner;
 
public class Main {
    static int n;
    static int[] dur;
    static int[] wei;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dur = new int[n];
        wei = new int[n];
        /******************************
         * 백트래킹을 이용해서 모든 경우를 구한다.
         * 이때 이미 깨진 경우와 쥔거 뺴고 다깨져 있는
         * 경우를 처리해서 깨진 계란의 최대값을
         * 구한다.
         *******************************/
        for(int i = 0; i < n; i++) {
                dur[i] = sc.nextInt();
                wei[i] = sc.nextInt();
        }
        solve(0);
        System.out.println(max);
    }
    static int max = 0;
    static int egg = 0;
    
    public static void solve(int hold) {
        if(hold == n) {
            max = Math.max(max, egg);
            return;
        }
        
        for(int target = 0; target < n; target++) {
            
            if(dur[hold] <= 0 || egg == n-1) {
                solve(hold+1);
                return;
            }
            
            if(dur[target] <= 0) continue;
            
            if(target == hold) continue;
            
            int target_dur = dur[target];
            int hold_dur = dur[hold];
            int egg_temp = egg;
            dur[target] -= wei[hold];
            dur[hold] -= wei[target];
            if(dur[target] <= 0) egg++;
            if(dur[hold] <= 0) egg++;
            solve(hold+1);
            
            dur[target] = target_dur;
            dur[hold] = hold_dur;
            egg = egg_temp;
        }
    }
        
}
 

참고 & 출처