백준 15732 JAVA: 도토리 숨기기

문제 설명📖

lower bound를 활용한 이분 탐색으로 목표하는 값을 찾는 문제로 이분탐색 문제를 별로 접해보지 못해 떠올리기 어려웠던 문제이다.

풀이 방법✏️

1. 풀이 과정

박스들을 lower bound를 활용한 이분 탐색을 진행하여 현재 보고 있는 박스까지 담겨져 있는 도토리의 개수를 찾고 이를 만족하는 박스들 중 최소 값(lower bound)을 구한다.

2. 유의 할 점

2-1. "현재 보고 있는 박스에 몇 번째 도토리가 담겨 있는가"는 "현재 보고 있는 박스까지 몇개의 도토리가 담겨져 있는가" 와 동일하다.

문제에서 찾는 마지막 도토리가 담겨져 있는 박스를 A라고 하면, A 박스 왼쪽에 있는 모든 박스에 들어있는 도토리의 합이 도토리의 총 개수와 동일해야 한다.

2-2. lower bound를 사용하지 않으면 올바르지 않은 답이 나올 수 있다.

• 특정 박스까지 담겨져 있는 도토리의 수가 총 도토리 수와 같은 경우가 여러가지가 존재하기 때문이다.
• "도토리의 개수가 정답과 일치하는 박스들 중 가장 앞에 있는 박스" == "규칙에 의거해 마지막 도토리가 담겨진 박스"

소스 코드(feat. 알찬 주석)⌨️

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

public class BJ_15732 {
    static int N, K, D;

    static Rule[] rules;
    static class Rule {
        int start, end, gap;

        public Rule(int start, int end, int gap) {
            this.start = start;
            this.end = end;
            this.gap = gap;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        rules = new Rule[K];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int gap = Integer.parseInt(st.nextToken());

            rules[i] = new Rule(start, end, gap);
        }

        System.out.println(findLastAcornBox());
    }

    private static int findLastAcornBox() { // 마지막 도토리가 담긴 박스 탐색
        int left = 0;
        int right = N;
        int minIdx = Integer.MAX_VALUE; // lower bound

        while (left <= right) {
            int mid = (left + right) / 2;

            long acornOrder = findAcornOrder(mid); // mid 번째 박스까지 몇개의 도토리가 들어있는 지 확인

            if (acornOrder >= D) { // 목표하는 값보다 더 크거나 같을 경우
                right = mid - 1;
                minIdx = Math.min(minIdx, mid); // lower bound 갱신
                continue;
            }

            left = mid + 1; // 목표하는 값보다 더 작을 경우
        }

        return minIdx;
    }

    /*
        lower bound를 사용하지 않을 경우 틀린 답이 나오게 된다.
        200 2 10
        100 150 10
        110 180 15
     */
    private static long findAcornOrder(int cur) { // cur번 째 박스에 몇 번째 도토리가 존재하는 지 계산
        long acornNum = 0; // cur 번째 박스까지 몇 개의 도토리가 존재하는 지 저장할 변수

        for (Rule rule : rules) {
            if (cur < rule.start) { // 현재 보고 있는 박스가 규칙의 시작 지점 보다 더 작은 경우
                continue;
            }

            int end = Math.min(rule.end, cur);
            acornNum += (end - rule.start) / rule.gap + 1;
        }

        return acornNum;
    }
}

• 문제 링크 : 도토리 숨기기