[이분탐색] 백준 - 랜선 자르기

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

1654번: 랜선 자르기

 

-문제해설

아직 이분탐색이 익숙하지가 않나보다. 한참 헤매다가 풀었다..

 

처음 입력받을 때 가장 큰 값을 찾기위해서 입력값에 대해서 Math.max() 메소드로 최대값을 찾아주고

이분탐색을 위해 start = 0, end = max값으로 설정한다.

그리고 while의 조건으로 start가 end보다 작거나 같으면 반복되도록 한다.

 

while문 안에서는 중간값을 찾기 위해 ( start+ end ) / 2를 mid에 저장하고

chk()라는 사용자 메서드를 호출한다.

 

chk() 메소드의 매개변수로는 입력받은 배열 arr, n, mid값이 주어진다.

chk 메소드에서는 각 입력값을 mid로 나눈 결과를 cnt에 누적합하고

마지막으로 cnt가 n보다 크거나 같으면 참, 아니면 거짓을 반환시킨다.

 

다시 while문으로 돌아와서 chk가 참이면 if문을 수행하고 거짓이면 else문을 실행한다.

만약 참일 경우에 mid값이 너무 작아서 각 랜선을 너무 많이 자른 것이므로 mid값을 증가시키기 위해 start = mid + 1로 재선언한다.

 

만약 거짓일 경우 mid값이 너무 커서 랜선은 너무 적게 자른 것이므로 mid값을 감소시키기 위해 end = mid - 1을 해준다.

 

이렇게 계속반복하다가 n값과 같거나 큰 mid값이 있으면 ans와 mid값을 Math.max() 메소드로 비교해서 가장 큰 값이 출력되도록 하면 성공이다.

 

 

파이썬 같은 경우에 자바와 똑같은 로직으로 코딩했는데 자꾸 0으로 나누는 경우가 발생해서 chk함수 호출 전에 mid가 0이면 1로 바꿔주는 코드를 추가했다.

 

 

-자바

package search;

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

public class BJ1654 {
	private static boolean chk( long[] a, int n, long mid ) {
		int cnt = 0;
		for( int i=0; i<a.length; i++ ) cnt += a[i] / mid;
		return cnt >= n;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int k = Integer.parseInt( st.nextToken() );	//가지고 있는 랜선개수
		int n = Integer.parseInt( st.nextToken() );	//필요한 랜선의 개수
		
		long arr[] = new long[k];
		long max = 0;
		for( int i=0; i<k; i++ ) {
			arr[i] = Integer.parseInt( br.readLine() );
			max = Math.max( max, arr[i] );
		}
		
		long ans = 0;
		long start = 1;
		long end = max;
		while( start <= end ) {
			long mid = (start+end) / 2;
			if( chk( arr, n, mid ) ) {
				ans = Math.max( ans, mid );
				start = mid + 1;
			} else end = mid - 1;
			
		}
		
		System.out.println( ans );
		
	}
}

 

 

-파이썬

def chk( arr, n, mid ):
    cnt = 0
    for i in range( len(arr) ):
        cnt += arr[i] // mid
    return cnt >= n

import sys
l = sys.stdin.readline
k, n = map( int, l().split() )
arr = [ int( l() ) for _ in range( k ) ]

ans = 0; start = 0; end = max( arr )
while start <= end:
    mid = (start+end) // 2
    mid = mid if mid != 0 else 1
    if chk( arr, n, mid ):
        ans = max( ans, mid )
        start = mid + 1
    else: end = mid - 1
print( ans )