백준으로 살펴보는 이분탐색과 부분합.

백준의 1654번 랜선자르기 문제를 해보면 탐색을 해서 적절한 값을 찾아야 한다.

이때 완전탐색을 하게되면 시간초과가 뜨게 된다. 그래서 이분탐색을 해야한다.

package baekjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Lan {
    private static final List<Integer> arr = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();

        for (int i = 0; i < k; i++) {
            arr.add(sc.nextInt());
        }

        long left = 1;
        long right = arr.stream().max(Integer::compareTo).get();
        long maxLength = 0;

        while (left <= right) {
            long mid = (left + right) / 2;
            long sum = 0;

            for (int item : arr)
                sum += item / mid;

            if (sum >= n) {
                maxLength = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(maxLength);
    }
}

근데 이분탐색을 쓰는 조건은 정렬 되어있는 데이터일 때 쓸 수 있다. 자, 위의 코드를 보면 arr는 정렬되지 않았다. 하지만 코드는 문제 없이 동작한다. 어떻게 동작하는 것일까?

 

이유는 탐색 대상이 정렬되기 때문이다.
찾고자 하는 sum값이 내림차순으로 데이터가 정렬되기 때문이다.

예를 들면 mid값이 커지면 커질수록 sum값은 작아질 수밖에 없다.
732, 406 두 데이터가 있다고 했을 때,

mid = 100 -> sum = 11
mid = 200 -> sum = 5

와 같이 내림차순 정렬된다.

 

자, 그럼 이제 2231번 부분합문제를 살펴보자.

처음에 문제를 보고 이분탐색으로 접근했더니 실패했다.
이유는 탐색 대상이 정렬되지 않기 때문이다.

 

200으로 생성할 수 있는 숫자는 200 + 2 + 0 + 0 = 202이다.
그런데 199로 생성가능 숫자는 199 + 1 + 9 + 9 = 218이다.

이처럼 부분합 문제는 탐색대상이 더 작은 수임에도 불구하고 생성 가능 숫자가 커질 수도 있다.
따라서 이러한 문제는 완탐으로 풀어야 한다.
223의 최소 생성자는 198이다.

package baekjoon;

import java.util.Scanner;

public class DivSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int left = 0;
        int right = n;
        int minValue = 0;

        // 이분탐색 실패 코드
//        while (left <= right) {
//            int mid = (left + right) / 2;
//            int sum = 0;
//
//            sum = mid + dfs(mid);
//            System.out.println("mid = " + mid);
//            if (sum == n)
//                minValue = mid;
//            if (sum >= n) {
//                right = mid - 1;
//            } else {
//                left = mid + 1;
//            }
//        }

        //완전탐색 코드
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum = i + dfs(i);
            if (sum == n) {
                minValue = i;
                break;
            }
        }
        System.out.println(minValue);
    }

    private static int dfs(int number) {
        if (number == 0)
            return 0;
        else {
            int result = number % 10;
            result += dfs(number / 10);
            return result;
        }
    }
}