알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘-1654(랜선 자르기)

By on October 9, 2019

문제

문제 링크 : 이분탐색-랜선 자르기 https://www.acmicpc.net/problem/1654

이분탐색 랜선 자르기 문제

풀이

  • 이 문제는 정말정말 매우 어려웠다. 두가지 문제점때문에 몇번을 틀리고 시간을 소모 했다.

    • 첫번째 int 선언 -> 랜선의 최대 길이가 N <= 2³¹-1 이므로 전체 길이를 더했을 때 int 최대 범위를 벗어 날 수 있음.
    • 두번째 문제에서 주어진 n 개만큼만 구하면 되는줄 알고 로직을 구현했음. 하지만 N보다 많이 만드는 경우 포함 이라고 설명 되어있음.

  • 풀이 시작

    • 주어진 랜선을 배열에 담는다. (int[] lines)
    • 주어진 랜선의 전체 길이를 구한다 (long sumLen)
    • 자를 수 있는 최대 길이 = sumLen / N(필요한 랜선의 갯수) 이다.
    • 1 ~ 자를 수 있는 최대 길이 내에서 이분 탐색을 한다.
    • lines 배열을 루프를 돌면서 mid 값으로 나누어(잘라서) 값을 더한다. (int cnt)
    • cnt >= N(필요한 랜선의 갯수)의 경우 최대 효율 값을 구해야 하기 때문에 (long maxLen) 에 저장한다.
    • 반복한다.

소스

  • 랜선 자르기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Backjoon_1654 {
	
	private static int n = 0; //필요한 랜선의 갯수
	private static int[] lines;
	private static long maxLen = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] inputA = reader.readLine().split(" ");
		
		int k = Integer.parseInt(inputA[0]);   //랜선의 개수
		n = Integer.parseInt(inputA[1]);
		
		lines = new int[k];
    
		long sumLen = 0;  //랜선의 전체 길이
		for(int i = 0; i < k; i++) {
			int len = Integer.parseInt(reader.readLine());
			lines[i] = len;
			sumLen += len;
		}

		Arrays.sort(lines); //정렬
		System.out.println(Bsearch(1, sumLen / n));     //이분탐색
	}

	public static long Bsearch(long left, long right) {
		int cnt = 0;
		long mid = (left + right) / 2;
		if(left > right) return maxLen;
		for (int i : lines) {
			cnt += i / mid;
		}
		if( cnt >= n) {
			if(mid > maxLen) {
				maxLen = mid;
			}
			return Bsearch(mid + 1, right);
		} else {
			return Bsearch(left, mid -1);
		}
	}
}

Back to blog