[BOJ 15732] 도토리 숨기기

15732번: 도토리 숨기기

조건

• 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)
• K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 넣는 규칙을 뜻한다. D는 모든 규칙으로 넣을 수 있는 도토리의 수보다 같거나 작다.

문제 재정의

• 도토리를 상자 앞에서부터 순차적으로 넣었을 때 “마지막” 도토리가 들어있는 **“상자의 번호”**를 찾는다.
• 상자의 개수가 1 ≤ N ≤ 1,000,000이기 때문에 최대 상자의 번호는 1,000,000

최악 계산

• 반복문으로 상자에 넣을 경우 A가 1이고 B가 N(1,000,000)인 경우만 입력으로 10000개가 들어왔다고 한다면, O(N * K) = 100억
• 이분 탐색을 고민

예외 조건

• D는 모든 규칙으로 넣을 수 있는 도토리의 수보다 같거나 작다.
  • D의 최대는 10억, 누적 합이 10억 * K(10000) → long으로 처리해야 한다.

계산 로직 정의

• 상자의 번호를 1과 N 사이에서 이분 탐색
• mid가 상자의 번호가 되고, 상자의 번호까지 왔을 때
  • 마지막 도토리보다 같거나 많이 줄 수 있다면 답의 후보이며 상자의 번호를 줄여보고
  • 아니라면 상자의 번호를 늘린다.
• 도토리의 개수는 K개의 규칙에 대하여
  • 각 규칙마다 상자의 시작 번호가 mid보다 크다면 continue
  • 아니라면 mid와 규칙의 마지막 상자 번호의 대소를 비교해서 범위를 재설정
  • 이후 계산
• O(KlogN)

package Baekjoon;

import java.io.*;
import java.util.*;
public class BOJ15732 {

    static int N,K,D;
    static int[][] rules;
    public static void main(String[] args) throws IOException{

        init();
        System.out.println(binarySearch());
    }

    private static int binarySearch() {

        int left = 1;
        int right = N;

        while (left <= right) {

            int mid = (left + right) / 2;

            long corns = cntOfCorns(mid);

            if (corns >= D) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return right + 1;
    }

    private static long cntOfCorns(int mid) {

        long sum = 0;

        int right = 0;
        int res = 0;
        for (int i = 0; i < K; i++) {

            if (rules[i][0] > mid) continue;

            right = Math.min(mid,rules[i][1]);
            res = (right - rules[i][0]);

            sum += res / rules[i][2] + 1;

        }

        return sum;
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);
        D = Integer.parseInt(input[2]);

        rules = new int[K][3];

        for (int i = 0; i < K; i++) {
            input = br.readLine().split(" ");
            rules[i][0] = Integer.parseInt(input[0]);
            rules[i][1] = Integer.parseInt(input[1]);
            rules[i][2] = Integer.parseInt(input[2]);
        }

        Arrays.sort(rules,(o1,o2) -> { return Integer.compare(o1[0],o2[0]);});

    }


}

 

 

Add : BOJ15732 도토리 숨기기 이분 탐색 풀이 · ssjjaa-algo/AlgoAndMySQL@317c649