[BOJ_16987] 계란으로 계란치기

설명

---

canBreak 부분이 추가가 되면서 맞았는데 

 

조건 중 아래 조건을 간과하였다.

1. 가장 왼쪽의 계란을 든다.
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.
   
   

제대로 읽고 문제 푸는 연습이 필요하다.

코드

---

 

package backtracking;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_16987 {
    static int N;

    static int ans;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(tk.nextToken());

        ans = Integer.MIN_VALUE;
        int arr[][] = new int[N][2];
        for(int i = 0; i < N; i++){
            tk = new StringTokenizer(br.readLine()," ");
            arr[i][0] = Integer.parseInt(tk.nextToken()); // Durability
            arr[i][1] = Integer.parseInt(tk.nextToken()); // Weight
        }
        go(arr,0);
        System.out.println(ans);
    }

    private static void go(int[][] arr, int idx) {
        if (idx == N) {
            int count = 0;
            for (int i = 0; i < N; i++) {
                if (arr[i][0] <= 0) {
                    count++;
                }
            }
            ans = Math.max(ans, count);
            return;
        }

        if (arr[idx][0] <= 0) {
            go(arr, idx + 1); // 현재 계란이 깨져있는 경우 다음 계란으로 이동
        } else {
            boolean canBreak = false;
            for (int i = 0; i < N; i++) {
                if (i != idx && arr[i][0] > 0) {
                    arr[i][0] -= arr[idx][1];
                    arr[idx][0] -= arr[i][1];
                    canBreak = true;
                    go(arr, idx + 1);
                    arr[i][0] += arr[idx][1];
                    arr[idx][0] += arr[i][1];
                }
            }
            if (!canBreak) {
                go(arr, idx + 1); // 아무것도 치지 않은 경우의 수
            }
        }
    }
}

16987번: 계란으로 계란치기