백준 2343번 기타 레슨

문제

나의 풀이

import java.util.*;

public class Main {
    static int a[] = new int[100000];
    static int n, m;
    static boolean go(int size) {
        int count = 1;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            if(sum + a[i] > size) { // 레슨의 합이 size를 넘을 때
                count += 1; // 새로운 블루레이 추가
                sum = a[i];
            } else {
                sum += a[i];
            }
        }
        return count <= m; // 블루레이 개수가 m개 이하인지 
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int left = 0;
        int right = 0;
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            left = Math.max(left, a[i]); // 레슨 크기의 최대값 구하기
            right += a[i]; // 레슨 크기의 합 구하기
        }
        
        int answer = 0;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(go(mid)) { // mid가 m개의 블루레이에 담을 수 있는 크기인 경우
                answer = mid;
                right = mid - 1; // 크기를 더 작게
            } else {
                left = mid + 1; // 크기를 더 크게
            }
        }
        System.out.println(answer);
    }
}

이분탐색으로 찾아야 하는 값은 블루레이의 크기이다.
M개의 블루레이에 답을 수 있으면 크기를 작게, 담을 수 없으면 크기를 크게 해서 탐색을 하면 된다.
최소(left)는 레슨 크기의 최대값이고 최대(right)는 레슨 크기의 합이다.
go 함수는 크기가 size인 블루레이로 녹화했을 때 M개 이하의 블루레이가 나오는지에 대한 여부를 판별하는 함수다.

결과

백준 13397번 구간 나누기 2

문제

나의 풀이

import java.util.*;

public class Main {
    public static int go(int[] a, int mid) {
        int n = a.length;
        int t1 = a[0];
        int t2 = a[0];
        int answer = 1;
        for(int i = 1; i < n; i++) {
            t1 = Math.min(t1, a[i]); // 구간의 최소값 구하기
            t2 = Math.max(t2, a[i]); // 구간의 최대값 구하기
            if(t2 - t1 > mid) {
                answer += 1; // 구간 추가
                t1 = a[i]; // 구간 최소값 초기화
                t2 = a[i]; // 구간 최대값 초기화 
            }
        }
        return answer; // 구간 개수 리턴
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int a[] = new int[n];
        int left = 0;
        int right = 0;
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            right = Math.max(right, a[i]); // 수의 최대값 구하기
        }
        
        int answer = right;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(go(a, mid) <= k) { // 구간 개수가 k 이하인 경우
                right = mid - 1; // 더 작게
                answer = Math.min(answer, mid); // 점수의 최소값 구하기
            } else {
                left = mid + 1; // 더 크게
            }
        }
        System.out.println(answer);
    }
}

구간의 점수를 결정하고 구간을 앞에서부터 차례대로 나눠보면 된다.

결과

백준 1300번 K번째 수

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long k = sc.nextLong();
        long left = 1;
        long right = n * n; // A[i][j]의 최대값은 n * n
        long answer = 0;
        while(left <= right) {
            long mid = (left + right) / 2;
            long count = 0;
            for(long i = 1; i <= n; i++) {
                count += Math.min(n, mid / i); // mid / i가 n을 넘어가는 경우엔 n으로
            }
            if(count >= k) { // k 이상인 경우
                answer = mid;
                right = mid - 1; // 더 작게
            } else {
                left = mid + 1; // 더 크게
            }
        }
        System.out.println(answer);
    }
}

정렬했을 때, k번째 위치라는 것은 그 수보다 작은 수가 k개라는 것과 같은 의미이다.

결과