[백준] 16987번 - 계란으로 계란치기 [Java]

https://www.acmicpc.net/problem/16987

 

[백준] 16987번 - 계란으로 계란치기 [Java]

[백준] 16987번 - 계란으로 계란치기 [Java]

[백준] 16987번 - 계란으로 계란치기 [Java]

[백준] 16987번 - 계란으로 계란치기 [Java]

---

1.  아이디어

 

중복 순열을 응용한 재귀 함수 + 백트래킹으로 시뮬레이션을 돌려 해결했다.

---

2. 문제풀이

 

중복 순열 기반의 solve 메서드를 먼저 작성했다. selIdx는 현재 손에 들 계란, for문의 i는 손에 든 계란으로 칠 계란을 의미한다.

그러면 재귀 함수는 selIdx를 파라미터로 들고 다니며 selIdx가 오른쪽 끝 계란까지 다 선택했을 때 종료되게 되고 이때 깨진 계란의 수를 세는 방식으로 구현했다. 다만 마지막 계란이 칠 수 있는 계란이 없을 경우 재귀 함수가 추가로 실행되지 않아서 cnt == egg.length - 1 이라는 조건을 추가했다.

 

solve 메서드는 문제 조건에 맞춰 현재 손에 들 계란이 깨진 계란이면 다음 계란으로 넘어가게 재귀 조건을 추가했고, for문에서는 현재 손에 든 계란으로 손에 들지 않은 계란을 쳐야하는 조건과 깨지지 않은 계란을 쳐야하는 조건을 추가해주고 이후 계란을 서로 친 후 깨진 계란 수에 따라 파라미터를 바꿔서 재귀를 돌린 후 다시 계란을 원상복구하는 방식으로 구현했다.

---

3. 코드

 

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

public class Main {

    private static class Egg {
        int S;
        int W;

        public Egg(int S, int W) {
            this.S = S;
            this.W = W;
        }
    }

    private static Egg[] eggs;
    private static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        eggs = new Egg[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            eggs[i] = new Egg(S, W);
        }

        solve(0, 0);

        System.out.println(ans);
    }

    // 중복 순열 기반 재귀 함수
    private static void solve(int selIdx, int cnt) {
        
        // 가장 오른쪽 계란까지 손에 든 이후인 경우 || 가장 오른쪽 계란이 칠 계란이 없는 경우
        if (selIdx == eggs.length || cnt == eggs.length - 1) {
            ans = Math.max(ans, cnt);
            return;
        }

        // 손에 들 계란이 깨진 계란인 경우
        if (eggs[selIdx].S <= 0) {
            solve(selIdx + 1, cnt);
            return;
        }

        for (int i = 0; i < eggs.length; i++) {
            
            // 손에 든 계란이랑 칠 계란이 동일한 경우
            if (selIdx == i) continue;
            
            // 칠 계란이 깨진 계란인 경우
            if (eggs[i].S <= 0) continue;

            // 계란 치기
            eggs[selIdx].S -= eggs[i].W;
            eggs[i].S -= eggs[selIdx].W;

            if (eggs[selIdx].S <= 0 && eggs[i].S <= 0) solve(selIdx + 1, cnt + 2);
            else if (eggs[selIdx].S <= 0 || eggs[i].S <= 0) solve(selIdx + 1, cnt + 1);
            else solve(selIdx + 1, cnt);

            // 계란 복구하기
            eggs[selIdx].S += eggs[i].W;
            eggs[i].S += eggs[selIdx].W;
        }
    }

}

---

4. 후기