문제

랜선 자르기

풀이

이 문제는 이분탐색 문제인데 배열을 주고 n개를 할수 있는 최대 길이를 구하는 문제다.
나중에 가면 최대길이를 주고 n개를 나눌수 있는 배열의 값들을 골라달라고 할것 같다. 어 이거 백설공주 난쟁이 문제인가.. 이 문제는 조금 이분탐색에서도 응용문제라 정답률도 실버답지않게 낮은편이다

1. min, max, mid 는 long 형으로 설정해야 한다. 2^31-1 까지가 범위기 때문이다
2. max 값을 구할때 +1을 연산 해주어야 한다

		long max = 0;
        for (int i = 0; i < k; i++) {
            len[i] = sc.nextInt();
            if (max < len[i]) {
                max = len[i];
            }
        }
        sc.close();

        max++;

• 이 부분은 후에 연산을 해줘야 할때 필요하다 min + max 에 피벗 값으로 정해질 mid 값으로 나누어 주어야할때 min, max가 1 일경우 mid pivot은 0이 되는데 이렇게 되면 0으로 나누어지기 때문에 런타임에러가 뜰것이다

3. min값이 max보다 커질때까지 반복문 안에서 이분탐색을 한다

		while (min < max) {
            mid = (min + max) / 2;
            long cnt = 0;
            for (int i = 0; i < len.length; i++) {
                cnt += len[i] / mid;
            }
            if (cnt < n) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }

• min 값을 max 값보다 크게 설정하기 위한 반복문이다. 그렇기 때문에 upper bound 라고 하는 것같다
• cnt 값은 mid 로 만든 랜선의 개수 값이다. cnt값이 만들어야 하는 값(n) 보다 작으면 max 더 짧게 잘라야 하기 때문에 최대 값인 max 값에 mid를 대입해준다
• 반대로 cnt 값이 n 보다 크다면 더 크게 잘라야 하기 때문에 min 값에 mid 값을 더해주어야 한다. 이경우 +1 을 해줘야하는데 이유는 4번과 연결된다

4. 마지막엔 min에서 -1을 연산해야 한다.

System.out.println(min - 1);

• 예외는 이것이다. 2개의 랜선을 가지고 2개를 만들어야 하는 경우에 1센치 짜리 랜선이 두개 씩 들어오는데 만약 이렇게 연산을 안하게 되면 값이 틀리는 경우가 생긴다.

이문제는 이 블로그 의 소스를 많이 참고 하게되었다. 진짜 binary search 정말 중독성이 있는 알고리즘 인것 같다.

전체 코드

전체 코드