[LeetCode] 1775 Closest Dessert Cost(Java)

1. 문제 설명

문제 링크: LeetCode 1775 - Closest Dessert Cost

요약: 주어진 예산 내에서 target 금액에 가장 가까운 디저트 비용을 만드는 문제입니다.

• 하나의 Base(필수)를 선택해야 합니다.
• 여러 종류의 Topping(선택)을 추가할 수 있으며, 각 토핑은 최대 2개까지 사용 가능합니다.
• target과의 차이가 동일한 비용이 여러 개라면, 더 낮은 비용을 선택합니다.

2. 핵심 아이디어

이 문제는 선택의 가짓수가 제한적이고(토핑당 0, 1, 2개), 모든 경우를 탐색해도 시간 내에 해결 가능한 백트래킹(Backtracking) 문제입니다.

• 완전 탐색: 모든 베이스 비용에 대해 각각 토핑을 추가하는 모든 경우의 수를 확인합니다.
• 상태 정의: dfs(index, currentCost) 함수를 통해 현재 고려 중인 토핑의 인덱스와 지금까지 쌓인 비용을 관리합니다.
• 가지치기(Pruning): 이미 현재 비용이 target을 넘어섰다면, 토핑을 더 추가하는 것은 target과의 거리를 멀어지게만 할 뿐이므로 탐색을 중단합니다.

3. 코드

Java

 

class Solution {
    int ret;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        // 초기값 설정 (첫 번째 베이스 비용으로 시작)
        ret = baseCosts[0];

        // 1. 모든 Base에 대해 DFS 수행
        for (int base : baseCosts) {
            dfs(0, base, toppingCosts, target);
        }

        return ret;
    }

    private void dfs(int index, int currentCost, int[] toppingCosts, int target) {
        int currentDiff = Math.abs(currentCost - target);
        int bestDiff = Math.abs(ret - target);

        // 2. 최적의 결과(ret) 갱신 로직
        if (currentDiff < bestDiff) {
            ret = currentCost;
        } else if (currentDiff == bestDiff) {
            // 차이가 같다면 더 작은 값을 선택
            ret = Math.min(ret, currentCost);
        }

        // 3. 기저 조건 및 가지치기
        // 모든 토핑을 고려했거나, 이미 target을 초과한 경우 중단
        if (index == toppingCosts.length || currentCost > target) {
            return;
        }

        // 4. 재귀 호출 (토핑을 0개, 1개, 2개 추가하는 경우)
        for (int i = 0; i <= 2; i++) {
            dfs(index + 1, currentCost + (toppingCosts[index] * i), toppingCosts, target);
        }
    }
}

4. 코드 포인트 해설

• ret 갱신 조건: currentDiff < bestDiff일 때뿐만 아니라, 거리가 같을 때 Math.min(ret, currentCost)를 사용하여 문제의 요구 조건(가장 작은 비용)을 충족했습니다.
• currentCost > target 가지치기: 토핑의 비용은 모두 양수이므로, 이미 target을 넘은 상태에서 토핑을 더하는 것은 의미가 없습니다. 이를 통해 탐색 효율을 높였습니다.
• 3진 트리 구조: 각 토핑 인덱스에서 선택지가 3개(0, 1, 2개)이므로, DFS는 최대 $3^{\text{topping length}}$의 깊이로 전개됩니다.

5. 성능 및 복잡도

• 시간 복잡도: 베이스의 개수를 $B$, 토핑의 개수를 $T$라고 할 때, **$O(B \times 3^T)$**입니다. $B, T \le 10$이므로 최대 연산 횟수는 약 $10 \times 3^{10} = 590,490$번으로 매우 안전하게 통과됩니다.
• 공간 복잡도: 재귀 호출의 깊이가 토핑의 개수 $T$에 비례하므로 **$O(T)$**의 스택 공간을 사용합니다.

6. 마치며

조합 가능한 경우의 수가 적절히 제한되어 있을 때 DFS/백트래킹이 얼마나 강력한지 보여주는 문제입니다. 특히 "차이가 같을 때 작은 값을 선택한다"는 디테일한 조건을 조건문에 녹여내는 것이 포인트였습니다.