11964 - Fruit Feast (Java)

🔗 문제 링크: 백준 11964번 - Hot Dogs?

---

📌 문제 설명

• 목표 점수 T 가 주어지고, 두 가지 점수 획득 방법 A, B가 주어진다.
• 한 번에 A점 또는 B점을 얻을 수 있음.
• 추가적으로 /2 연산을 한 번만 수행 가능 (현재 점수를 절반으로 줄이는 것).
• T 이하에서 최대 점수를 구하는 문제.

---

💡 풀이 방법: BFS 탐색 (최적 해 보장)

🔹 1️⃣ DP 접근 시도 (실패)

처음에는 DP로 해결을 시도했으나, 최적 부분 구조(Optimal Substructure) 를 만족하지 않아 실패.

• /2 연산이 비선형적인 변화를 만들며, 이전 상태의 최적해를 재사용할 수 없음.
• 즉, dp[i] = max(dp[i - A], dp[i - B], dp[i / 2]) 같은 점화식을 만들 수 없음.
• ✅ 그래서 BFS를 사용하여 최적 해를 찾는 방식으로 전환.

---

🔥 BFS를 활용한 풀이

BFS를 활용하면, 최소한의 연산으로 최대 점수를 찾을 수 있음.

🔹 BFS 탐색 과정

1. Queue<int[]> 를 사용하여 탐색 (현재 점수, /2 연산 사용 여부).
2. 매번 A 또는 B를 더한 값이 T 이하인지 확인 후 큐에 추가.
3. /2 연산을 아직 사용하지 않았다면 한 번만 실행 가능.
4. 최대 점수(answer)를 계속 갱신하며 BFS 탐색 진행.

---

📝 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static StringTokenizer st;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int T, A, B;
    private static boolean[][] visited; // [현재 점수][/2 연산 사용 여부]

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        visited = new boolean[T + 1][2]; // 최대 T까지 탐색
        int answer = 0;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, 0}); // (현재 점수, /2 연산 사용 여부)

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int point = cur[0];
            int isDrink = cur[1];

            answer = Math.max(answer, point); // 최대 점수 갱신
            if (answer == T) break; // 최대 점수에 도달하면 종료

            // A 점수를 추가할 수 있는 경우
            if (point + A <= T && !visited[point + A][isDrink]) {
                visited[point + A][isDrink] = true;
                queue.add(new int[]{point + A, isDrink});
            }

            // B 점수를 추가할 수 있는 경우
            if (point + B <= T && !visited[point + B][isDrink]) {
                visited[point + B][isDrink] = true;
                queue.add(new int[]{point + B, isDrink});
            }

            // /2 연산을 아직 사용하지 않았다면 한 번만 실행 가능
            if (isDrink == 0 && !visited[point / 2][1]) {
                visited[point / 2][1] = true;
                queue.add(new int[]{point / 2, 1});
            }
        }

        System.out.println(answer);
    }
}

---

✅ 코드 최적화 및 개선

🚀 1️⃣ BFS 탐색 최적화

• 불필요한 /2 연산 방지
  • /2 연산을 적용할 때, point / 2 == point이면 큐에 넣을 필요 없음. (0, 1, 2 등)
• visited 배열 활용 최적화
  • visited[point][isDrink]를 사용하여 중복 방문 방지.

🚀 2️⃣ BFS vs DP 비교

방법	시간복잡도	최적해 보장	설명
DP	🚫 불가능	🚫 보장 X	/2 연산이 비선형적이라 점화식을 만들 수 없음
BFS	✅ O(T log T)	✅ 최적해 보장	최단 경로 탐색 방식으로 정확한 정답 도출 가능

---

📌 결론

❌ DP로 풀 수 없는 이유

🚫 최적 부분 구조 (Optimal Substructure)를 만족하지 않음
🚫 중복 부분 문제 (Overlapping Subproblems)를 활용할 수 없음
✅ 따라서, BFS로 해결해야 함.

✅ BFS 최적화

• Queue<int[]>를 활용한 상태 탐색
• visited[][]을 사용하여 중복 탐색 방지
• 최대 점수를 갱신하며 탐색 진행