[백준] S3 1654 랜선 자르기 (java)

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

풀이

 

1) 가지고 있는 랜선을 배열에 담음(long)

2) 0~Long.Max_Value의 범위에서 이분탐색으로 가장 최적의 해를 찾을거임

2-1) 배열의 원소들을 이분탐색으로 나온 값으로 나눈 몫을 더해서

2-2) K보다 크면 left를 바꾸고 작으면 right를 바꿈. 

2-3) 조건에 맞는 최댓값을 갱신해나감

3) 출력

 

주의사항

 

1) 그리디 아님

 

package com.baekJoon;

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

public class BJ_S3_1654_랜선자르기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,K;
	static long map[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		
		map = new long[N];
		
		for(int n=0; n<N; n++) {
			map[n] = Long.parseLong(input.readLine());
		}
		Arrays.sort(map);
		
//		System.out.println(Arrays.toString(map));
		long left = 0;
		long right = Long.MAX_VALUE;
		long answer = 0;
		long mid = 0;
		long max = 0;
		while(left <= right) {
			answer = 0;
			mid = (right + left) / 2;
			for(int i=0; i<N; i++) {
				answer += map[i] / mid;
			}
			
			if(answer >= K) {
				left = mid+1;
				if(max < mid) {
					max = mid;
				}
			}else {
				right = mid-1;
			}
		}
		System.out.println(max);
	}

	static String src =
			"4 11\r\n" + 
			"802\r\n" + 
			"743\r\n" + 
			"457\r\n" + 
			"539";
}

 

 

후기

 

처음에 그리디문제 인줄알고 오름차순으로 정렬하여 제일 작은놈으로 다른애들을 나눠서 몫의 합이 K보다 크거나 같을때 까지 하나씩 줄이는 문제인줄 알았지만 범위가 어마무시해서 무조건 빠른 알고리즘이 필요한 문제였다.

뭔가 이분탐색은 정말 부족했던 영역인데 이런 문제들을 풀면서 부족한점을 조금이나마 메꿀 수 있다는 점이 너무 좋았다.