0. 문제

1. 문제 상황
   연속된 집들이 있음 (각 집에는 일정 금액이 있음).
   도둑이 집을 털려 함.
   하지만 인접한 집은 털지 않음 (즉, 두 개의 연속된 집을 선택할 수 없음).
   도둑은 최소한 k개의 집을 털어야 함.
2. 입력
   nums[i]: i번 집에 숨겨진 돈 (nums는 정수 배열).
   k: 최소한 털어야 하는 집의 개수 (k는 정수).
3. 출력
   도둑의 "최소한 가져가야 하는 최대 금액"을 구하는 것.

즉, 도둑이 집 k개를 털었을 때, "가장 큰 금액을 가진 집"이 가능한 한 최소가 되도록 해야 함.

예제 1:

• 입력: nums = [2,3,5,9], k = 2
• 출력: 5
• 설명:

  2개 이상의 집을 털 수 있는 방법은 다음과 같습니다:

  • 집 0번과 2번을 털기 → max(nums[0], nums[2]) = max(2, 5) = 5
  • 집 0번과 3번을 털기 → max(nums[0], nums[3]) = max(2, 9) = 9
  • 집 1번과 3번을 털기 → max(nums[1], nums[3]) = max(3, 9) = 9

  이 중에서 최소값을 선택해야 하므로, min(5, 9, 9) = 5를 반환합니다.

예제 2:

• 입력: nums = [2,7,9,3,1], k = 2
• 출력: 2
• 설명:

  총 7가지 방법이 존재하지만, 가장 작은 도둑의 능력치(capability)를 가지는 경우는 집 0번과 4번을 털 때입니다.
  max(nums[0], nums[4]) = max(2, 1) = 2
  따라서, 2를 반환합니다.

제한사항:

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= (nums.length + 1)/2

1. 정답

시간 복잡도

$O(Log(N)∗K)$

문제점

이진 탐색을 알고 있었음에도 문제에 어떻게 적용해야 되는지 파악하지 못했음.
찾고자 하는 값이 최소값이기 때문에, reward를 바탕으로 이진 탐색을 구현해야 했음.
목표값을 정하고 이에 맞는 경우가 몇가지인지 살펴보는 것이 아니라, 모든 경우를 일일이 다 따져서 그 경우의 수에서 최소값을 찾으려고 함.

이진 탐색을 고려해야 하는 경우

1. 정렬된 배열에서 특정 값 찾기

2. Lower Bound / Upper Bound 탐색:

   • Lower Bound: target 이상의 첫 번째 위치를 찾음.
   • Upper Bound: target 초과의 첫 번째 위치를 찾음

3. 특정 조건을 만족하는 최적값 찾기 (Parametric Search):

   • 가능한 X 중에서 최소/최대 값을 찾는 문제, MiniMax/Maximin

4. 배낭 문제 (DP + 이진 탐색)

5. 제곱근, N제곱근 구하기

논리

1 <= nums[i] <= 109를 바탕으로minReward와 maxReward를 설정.
이진 탐색의 기본 틀인 while (minReward < maxReward) 구성.
midReward를 계산하고 이를 바탕으로 midReward가 최대가 될 수 있는 인접하지 않은 집의 경우의 수를 계산.
계산한 경우의 수가 k개 이상일 경우, 더 적은 midReward로도 k개의 집을 도둑질할 수 있는지 재검토. 즉, maxReward = midReward;로 범위 재조정.
k개의 집을 도둑질하지 못했을 경우에는 더 많은 midReward가 필요함. 즉, minReward = midReward + 1;로 범위 재조정.
최종적으로 minReward가 maxReward랑 같아지는 시점 발생. 이 지점이 최대값의 최소치.

구현

class Solution {
    public int minCapability(int[] nums, int k) {
        // 이진 탐색을 위한 변수 설정.
        int minReward = 1;
        int maxReward = 0;
        int totalHouses = nums.length;

        for (int num: nums)
            if (maxReward < num)
                maxReward = num;

        // 이진 탐색으로 k개의 집을 도둑질할 때 얻을 수 있는 최소 최대값 보상 찾기.
        while (minReward < maxReward) {
            int midReward = (minReward + maxReward) / 2;
            int possibleThefts = 0;

            for (int index = 0; index < totalHouses; ++index) {
                if (nums[index] <= midReward) { // midReward 이하를 얻을 수 있다면
                    possibleThefts += 1; // 도둑질을 하고
                    index++; // 인접하지 않은 다음 집으로 이동
                }
            }

            // midReward로 k개 이상의 집을 도둑질 할 수 있다면 midReward가 더 적어도 가능한지 확인.
            if (possibleThefts >= k)
                maxReward = midReward;
            // midReward로 k개의 집을 도둑질하지 못한다면 midReward가 더 커야함.
            else
                minReward = midReward + 1;
        }

        return minReward;
    }
}