문제 1: 일별 최대 작업 시간 최소화 (LCP 12)

특정 프로젝트 진행 시 전체 작업량을 $N$개의 과제들로 나누어 $M$일 동안 처리해야 하는 상황을 가정합니다. 각 과제에는 고유한 수행 시간이 존재하며, 반드시 순서대로 실행되어야 합니다. 다만, 매일 한 번씩 전문가의 도움을 받아 특정 과제의 소요 시간을 제로로 할 수 있는 기회가 주어집니다. 이 조건 하에서 $M$일 간의 작업 중 가장 많이 소모된 하루의 시간을 최소화하는 값을 구하는 문제가 목표입니다.

접근 방법

• 최대 비용을 기준으로 이진 탐색 (Binary Search) 을 적용할 수 있습니다. 만약 하루에 $K$시간 이하로 가능하다면, 그보다 긴 시간인 $K+1$시간도 항상 가능합니다. 이러한 단조 증가 성질을 활용하여 가능한 최소한도의 상한선을 찾아냅니다.
• 각 날마다 가장 시간이 오래 걸리는 과제를 스킵하면 나머지 시간 합이 허용 범위 내에 들어오는지 그리디하게 검증합니다.

구현 코드 (C++)

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    // 주어진 제한 시간 limit 으로 모든 작업을 days 만큼의 날짜 안에 끝낼 수 있는지 확인
    bool canCompleteInDays(const std::vector<int>& costs, int days, int limit) {
        int requiredDays = 1;
        int currentSum = 0;
        int maxCostInCurrentDay = 0;

        for (int duration : costs) {
            // 현재 과제를 포함시켰을 때, 가장 비싼 것을 제외하고 나라도 여전히 limit 을 초과하는지 판단
            // 두 가지 경우: 1) 추가 후 총합 - 최댓값 <= limit 2) 현재 값이 새로운 최댓값이어도 조건 만족
            if (std::max(currentSum, duration) + duration - std::max(maxCostInCurrentDay, duration) <= limit) {
                 currentSum += duration;
                 maxCostInCurrentDay = std::max(maxCostInCurrentDay, duration);
            } else {
                // 현재 날짜의 용량이 부족하므로 새 날짜를 시작
                ++requiredDays;
                if (requiredDays > days) return false;
                
                // 새 날짜 초기화
                currentSum = duration;
                maxCostInCurrentDay = duration;
            }
        }
        return true;
    }

    int minimizeMaxTime(std::vector<int>& timeRequired, int m) {
        int n = timeRequired.size();
        if (n <= m) return 0; // 작업 개수가 날짜보다 적으면 모두 스킵 가능
        
        int low = *std::min_element(timeRequired.begin(), timeRequired.end());
        int high = std::accumulate(timeRequired.begin(), timeRequired.end(), 0);
        int answer = high;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (canCompleteInDays(timeRequired, m, mid)) {
                answer = mid;
                high = mid - 1; // 더 작은 값 시도
            } else {
                low = mid + 1; // 값이 너무 작음
            }
        }
        return answer;
    }
};

문제 2: 구간 내 정수 선택 시 최소 거리 극대화 (3281)

$N$개의 서로 다른 닫힌 구간 $[start[i], start[i] + d]$가 주어집니다. 각 구간에서 정확히 하나의 정수를 선택해야 하며, 이때 선택된 $N$개의 정수 중 어떤 두 숫자의 절댓값 차이가 최소로 나타나는 값을 점수로 정의합니다. 가능한 점수의 최대값을 반환해야 합니다.

핵심 논리

1. 목표는 선택된 숫자들 사이의 최소 절대 차이를 최대화하는 것입니다. 이는 이분 탐색의 전형적인 패턴인 "최대를 구하라" 유형에 해당합니다.
2. 이분 탐색의 중간 값 ($mid$) 을 가정한 최소 차이라고 볼 때, 모든 선택된 쌍의 차이가 이 값 이상인지 확인하는 검증 함수를 작성합니다.
3. 검증 단계에서는 구간들을 시작점 기준으로 정렬한 뒤, 이전 선택값으로부터 가능한 최솟값으로 이동하면서 각 구간 범위를 이탈하지 않는지 체크하는 그리디 전략을 사용합니다.

구현 코드 (C++)

#include <vector>
#include <algorithm>
#include <climits>

class RangeMaximizer {
public:
    // 주어진 최소 거리 diff 를 유지하면서 모든 구간에서 숫자를 고를 수 있는지 확인
    bool isValid(const std::vector<int>& starts, int rangeSize, int diff) {
        int lastPosition = INT_MIN;
        
        for (int start : starts) {
            // 이전 위치에서 diff 만큼 떨어진 곳이 이번 구간의 시작점보다 크다면 그 위치에 설정
            // 아니면 구간의 시작점에 설정 (가능한 가장 왼쪽)
            int currentPos = std::max(lastPosition + diff, start);
            
            // 만약 계산된 위치가 구간 범위 [start, start+d] 를 벗어난다면 불가능
            if (currentPos > start + rangeSize) {
                return false;
            }
            lastPosition = currentPos;
        }
        return true;
    }

    int calculateMaxScore(std::vector<int>& intervalStarts, int d) {
        // 최적화를 위해 구간 시작점을 오름차순 정렬
        std::sort(intervalStarts.begin(), intervalStarts.end());

        int leftBound = 0;
        int rightBound = INT_MAX;
        int result = 0;

        while (leftBound <= rightBound) {
            int midDist = leftBound + ((rightBound - leftBound) >> 1);
            
            if (isValid(intervalStarts, d, midDist)) {
                result = midDist;      // 성공했으므로 더 큰 거리 시도
                leftBound = midDist + 1;
            } else {
                rightBound = midDist - 1; // 실패했으므로 거리 축소
            }
        }
        return result;
    }
};