<stdio.han>

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- 파라메트릭 서치

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int K, N;
    static long left = 1, right = Integer.MIN_VALUE;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new int[K];

        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            right = Math.max(right, arr[i]);
        }

        parametricSearch();

        br.close();
    }
    static void parametricSearch() {
        while (left <= right) {
            long mid = (left + right) / 2;
            long LAN = 0;
            for (int i = 0; i < arr.length; i++) {
                LAN += (arr[i] / mid);
            }
            if (LAN>=N){
                left = mid + 1;
            } else if (LAN < N) {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

[풀이]

- left, right, mid 를 long으로 설정해주어야 한다.

- left의 최소값이 1이어야 한다. 그렇지 않으면 divide by zero 오류가 발생한다. 예를들어 모든 가지고있는 랜선의 길이가 1이고 left가 0일 경우 mid가 0이 된다.

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- 파라메트릭 서치

- 이분탐색

[코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] trees = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        int left = 0;
        int right = -1;
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, trees[i]); // 나무의 최대 높이 이상으로는 자를 수 없기때문에 최대값 구하기
        }

        while (left <= right) { // left가 right를 넘어서기 전까지 반복
            int mid = (left + right) / 2;
            long tree = 0; // 범위를 초과해서 long
            for (int i = 0; i < N; i++) {
                if (trees[i] > mid) {
                    tree += trees[i] - mid;
                }
            }
            if (tree >= M) { // 너무 많이 가져갔거나 정확히 가져갔을 경우
                left = mid + 1;
            } else if (tree < M) { // 너무 적게 가져갔을 경우
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

[풀이]

• 이진 탐색 : 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이. 
• 파라메트릭 서치 : 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘.

이진 탐색은 값들이 주어지고 파라메트릭 서치는 범위가 주어진다.

이진탐색과 비슷하지만 약간 다르다. 솔직히 이해가 정확히 가지는 않는다. 

[참조한 글]

https://loosie.tistory.com/551