<Algorithm> 174. 랜선자르기(BJO)

1. 1654번 랜선자르기(BJO)

   사용 알고리즘 :  이분탐색

• 딱 그 갯수에 맟추는 것인 줄 알았는데 그 이상이 되도 상관이 없었다...

• 이분탐색의 경우 연산하면서 int 범위를 벗어나는 경우가 발생하므로 long형을 고려해야하는 것을 깨달았다.

문제에 대한 접근&생각

1. 랜선길이가 231-1 범위를 가진다 -> 이분탐색!
2. 자를수 있는 최대의 길이를 출력 -> 탐색기준!
3. 랜선의 길이가 int형의 최대값이므로 여기 까지 탐색해야함 -> int형 대신 long! 

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int k = sc.nextInt();         int n = sc.nextInt();         int[] lan = new int[k];         long max = 0;         /****************************          * 최대길이를 기준으로 이분탐색을 하여          * k개 이상을 만족하는 길이 중 최대값을          * 찾아 출력한다.          ****************************/         for(int i = 0; i < k ; i++) {             lan[i] = sc.nextInt();             max = Math.max(max, lan[i]);         }         long start = 0;         long end = max+1;         long ans = 0;         while(start<end) {             long mid = (start+end)/2;             long count = 0;             for(int i = 0; i < lan.length; i++) {                 count+= lan[i]/mid;             }             if(count >= n) {                 ans = Math.max(ans, mid);                 start = mid+1;             }else {                 end = mid;             }         }         System.out.println(ans);     } }   Colored by Color Scripter

cs

 

얻은 것

• int[] lan =Arrays.stream(new int[K]).map(i->sc.nextInt()).toArray() 으로 구현 가능