[백준/JAVA] 16987번: 계란으로 계란치기

🔺 문제

16987번: 계란으로 계란치기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, max = Integer.MIN_VALUE;
    static int[] durability, weight;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        durability = new int[N];    // 내구성 배열
        weight = new int[N];        // 무게 배열
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            durability[i] = Integer.parseInt(st.nextToken());
            weight[i] = Integer.parseInt(st.nextToken());
        }
        
        back(0);
        System.out.println(max);
    }
    
    private static void back(int depth) {
        // 마지막 계란인 경우
        if(depth == N) {
            int cnt = 0;
            
            for(int i = 0 ; i < N ; i++) 
                if(durability[i] <= 0)  // 깨진 계란 개수 구하기
                    cnt++;
            
            max = Math.max(max, cnt);
            return;
        }
        
        // 내구성이 0 이하면, 다음으로 넘어가기
        if(durability[depth] <= 0)
            back(depth + 1);
        else {
            boolean broken = false; // 깰 계란 있는지 확인용 변수
            
            for(int i = 0 ; i < N ; i++) {
                if(i == depth || durability[i] <= 0)    // 같은 계란이거나 내구성이 0 이하인 경우, 깰수 X
                    continue;
                
                broken = true;  // 깰 계란 존재
                
                // 두 계란 내구성 감소
                durability[i] -= weight[depth];
                durability[depth] -= weight[i];
                
                back(depth + 1);
                
                // 다음 경우의 수 위해 원상복구
                durability[i] += weight[depth];
                durability[depth] += weight[i];
            }
            
            // 깰 계란이 없으면, 다음으로 넘어가기
            if(!broken)
                back(depth + 1);
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹 & 브루트포스
- for문 안에서 연산을 하고, 조건에 맞춰 재귀호출

 

---

🔺 다른 풀이들

max를 구하는 방법이 약간 다르다.

백준 16987 - 계란으로 계란치기

 

---

💬 느낀 점

기본은 브루트포스를 잘 하고 조건문을 빠뜨리지 않고 쓰는 것 같다.

조합/순열 구하는 단순 백트래킹 문제는 풀겠는데

이렇게 조금이라도 조건을 더하면 못 풀다니...

 

다음 복습 때는 혼자 힘으로 풀고 싶다!

 

 

1회독	2회독	3회독	4회독	5회독
V	240601

 

 

(+240601 2회독 : 15676KB, 188ms)

개인적으로 이 풀이가 더 깔끔하니 좋은 것 같당.

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, answer;
    static int[] S,W;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        S = new int[N]; // 계란 내구도
        W = new int[N]; // 계란 무게
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            S[i] = Integer.parseInt(st.nextToken());
            W[i] = Integer.parseInt(st.nextToken());
        }
        
        dfs(0, 0);  // 0번째 계란부터 시작, 깨진 계란 수
        System.out.println(answer); // 깰 수 있는 최대 몇 개의 계란
    }
    
    private static void dfs(int depth, int cnt) {   // cnt: 깨진 계란 수
        // 마지막 계란까지 다 들었으면 종료
        if(depth == N) {
            answer = Math.max(answer, cnt);
            return;
        }
        
        // 손으로 든 계란이 이미 깨졌거나, 모든 계란이 이미 다 꺠진 경우 > 다음 계란 들기
        if(S[depth] <= 0 || cnt == N-1) {
            dfs(depth + 1, cnt);
            return;
        }
        
        int tmpCnt = cnt;   // 깨진 계란 수 원상복구 위해 저장용
        
        for(int i = 0 ; i < N ; i++) {
            // 손으로 들고 있는 계란 = 부딪히려고 하는 계란인 경우, 계란이 이미 깨져있는 경우 통과
            if(i == depth || S[i] <= 0) continue;
            
            // 계란 부딪히기
            S[i] -= W[depth];
            S[depth] -= W[i];
            
            if(S[depth] <= 0)   cnt++;  // 손에 든 계란이 깨지면 +1
            if(S[i] <= 0)       cnt++;  // 타겟이 된 계란이 깨지면 +1
            
            dfs(depth + 1, cnt);    // 다음 계란 들기
            
            // 원상복구
            S[i] += W[depth];
            S[depth] += W[i];
            cnt = tmpCnt;
        }
    }
}
 

---

(참고)

[백준_16987번] 계란으로 계란치기

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