백준_16987_계란으로계란치기

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

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

문제를 통해 한쪽 방향으로 쭉 진행되는 것을 알 수 있음

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

public class Main {
    static int N;
    static int[] S;
    static int[] W;
    static int ans = 0;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        S = new int[N];
        W = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            S[i] = Integer.parseInt(st.nextToken()); // 내구도
            W[i] = Integer.parseInt(st.nextToken()); // 무게
        }

        dfs(0);

        System.out.println(ans);
    }

    private static void dfs(int idx) {
        //종료
        if(idx == N) {
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                if (S[i] <= 0) {
                    cnt++;
                }
            }
            ans = Math.max(ans, cnt);
            return;
        }

        //확장
        if (S[idx] <= 0) { // 손에 들 계란이 부셔졌으면 다음거
            dfs(idx + 1);
            return;
        }

        boolean canHit = false;
        
        for (int i = 0; i < N; i++) {
            if (i == idx || S[i] <= 0) {
                continue;
            }
            canHit = true;
            S[idx] -= W[i];
            S[i] -= W[idx];

            dfs(idx + 1);

            S[idx] += W[i];
            S[i] += W[idx];
        }
        if (!canHit) { // 더이상 칠것이 없어도 다음거
            dfs(idx + 1);
        }
    }
}

• boolean canHit = false; 플래그를 사용하는 것!
• S[i] 로 깨졌는지 안깨졌는지 파악 가능하기 때문에 boolean[] crushed 배열을 따로 둘 필요가 없다.

	if (S[idx] <= 0) { // 손에 들 계란이 부셔졌으면 다음거
            dfs(idx + 1);
            return;
        }

• if (S[idx] <= 0): 현재 공의 내구도가 0 이하이면 이미 부서진 상태
• dfs(idx + 1): 다음 공을 확인하기 위해 재귀적으로 호출합니다.
• return;: return; 을 통해 dfs 함수를 종료! 👉 즉, 현재 공과의 충돌 시뮬레이션을 더 이상 진행하지 않고 다음 공으로 바로 넘어가는 것!

🤔 return; 을 사용하지 않으면, 현재 공이 부서진 상태임에도 불구하고 for 루프를 통해 다른 공과의 충돌 시뮬레이션을 계속 수행하게 된다!

그럼 아래에도 return??

	if (!canHit) {
            dfs(idx + 1);
        }

• 현재 메서드의 끝에 도달하게 되므로, 사실상 return 문이 필요하지 않음
• 하지만, 가독성을 위해 return을 추가할 수는 있음! (필수 X)