[Algorithm] 백준 이분탐색 문제 - 랜선 자르기(1654) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 이분탐색 문제 랜선 자르기 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

1. 풀이 소스

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = parseInt(st.nextToken());
        int n = parseInt(st.nextToken());

        int[] arr = new int[k]; // k개의 값을 저장할 배열
        long max = 0; // 최대값 저장 (가장 긴 랜선을 줄여 나가야 가장 큰 길이를 구할 수 있음)

        for (int i = 0; i < k; i++) {
            arr[i] = parseInt(br.readLine());
            if (max < arr[i]) max = arr[i]; // 최대값 업데이트
        }

        max++; //
        long min = 0;
        long mid = 0;

        while (min < max) { // 이분탐색으로 min < max인 조건으로 루프
            mid = (max + min) / 2; // 중간 값 설정하기

            long count = 0; // 카운트 개수 0 초기화

            for (int j : arr) {
                count += (j / mid); // count를 업데이트
                if (count >= n) break; // 개수가 n 보다 크면 종료
            }

            if (count < n) max = mid; // count
            else min = mid + 1; // upper bound로 min 값 증가
        }

        System.out.println(min - 1);
    }
}

 

2. 풀이 중점 사항

 

이번 문제는 이분 탐색의 upper bound를 활용하는 것이 중점 사항이었습니다.

도중에 47%에서 메모리 초과가 발생하여, 하단의 블로그를 참고하였습니다.

 

upper bound 방법은 이분 탐색의 한 종류로, 주어진 값보다 처음으로 큰 원소를 찾는 알고리즘입니다. 이분탐색의 차이점은 이분 탐색은 정확하게 특정 값을 찾는다면, upper bound는 이름처럼 가장 근접하게 큰 원소를 찾는 것이라고 설명할 수 있습니다.

예를 들어, min = 199, max = 201이 있다면, mid = (min + max) / 2 = 200이 됩니다. 

count < n이 성립하지 않으므로 min을 mid + 1 추가합니다. 이 과정에서, min < max 조건이 위배되게 되므로,

min = 201 상태에서 종료됩니다. 

upper bound는 앞 서 정의한 것처럼 가장 근접하게 큰 원소를 찾는 것이므로, 우리의 목표인 200보다 1 큰 값을 찾게 됩니다.

따라서, min - 1로 문제를 해결할 수 있었습니다.

 

이상으로 백준 랜선 자르기 풀이를 마치도록 하겠습니다. 감사합니다!!! 

 

 

참고 블로그: https://st-lab.tistory.com/269