[백준][Java] 15732 - 도토리 숨기기

문제 정보

https://www.acmicpc.net/problem/15732

 

 

난이도 : G2

유형 : 이분탐색

---

문제 풀이

주어진 도토리를 주어진 규칙들을 통해서만 박스에 모두 담을 때 마지막 박스 번호를 찾아야 한다.

즉 박스를 왼쪽부터 사용하되 가장 적게 사용하여야 하며 마지막으로 사용한 박스 번호를 찾으면 된다.

최적의 박스 번호는 이분 탐색으로 찾을 수 있다.

 

시간 복잡도는 박스의 개수인 N을 기준으로 O(NlogN) 걸린다.

 

left 포인터는 규칙 값으로 입력되는 A의 최솟값으로 설정

right 포인터는 규칙 값으로 입력되는 B의 최댓값으로 설정

 

각 구간에서 도토리 개수를 구하는 공식

public int getCount(int target) {
    if (target < start) {
        return 0;
    }
    return ((Math.min(target, end) - start) / interval) + 1;
}

 

(target -> left와 right의 mid 값이며 박스 번호를 의미)

 

1. target이 해당 규칙의 A값보다 작으면 도토리 개수가 0

2. target이 A ~ (B, target 중 작은 값) 사이에 있으면  도토리 개수는 ((Math.min(target, B) - A) / interval) + 1

---

코드

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

public class Main {

    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static final StringBuilder sb = new StringBuilder();
    public static StringTokenizer st;

    private int N;
    private int K;
    private int D;
    private List<Rule> rules;

    private boolean check(int mid) {
        long cnt = 0L;
        for (Rule rule : rules) {
            cnt += rule.getCount(mid);
        }
        return cnt >= D;
    }

    private void solution() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        rules = new ArrayList<>();
        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 interval = Integer.parseInt(st.nextToken());
            rules.add(new Rule(start, end, interval));

            left = Math.min(left, start);
            right = Math.max(right, end);
        }

        left -= 1;
        while (left + 1 < right) {
            int mid = (left + right) >> 1;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        System.out.println(right);
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.solution();
    }

    static class Rule {

        int start;
        int end;
        int interval;

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

        public int getCount(int target) {
            if (target < start) {
                return 0;
            }
            return ((Math.min(target, end) - start) / interval) + 1;
        }
    }
}