[DAY38] 99클럽 코딩테스트 JAVA 백준 랜선자르기 1654번

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

 

 

백준 1954번 문제를 풀기 위해서는 이진탐색 을 활용하면 된다.

---

 

🌘 문제 이해하기

• 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 한다. 
• 오영식은 자체적으로 K개의 랜선을 가지고 있다. (랜선의 길이는 제각각이다.)
• 랜선을 모두 같은 길이로 만들고 싶기 때문에 오영식의 랜선을 잘라서 K 개의 랜선을 만들어야 한다.
• 만들 수 있는 최대 랜선의 길이를 구하여라 

---

🌗 문제 자세히보기

 

🚩랜선의 최대값 길이는 int 형식의 범위를 벗어난다.  그래서 랜선의 길이에 대해서는 long 형식으로 지정해줘야 한다.

- int     :  -2,147,483,648 ~ 2,147,483,647
- long  : -9223372036854775808 ~ 9223372036854775807

 

• 이분탐색 을 활용하여 최소값과 최대값을 구한다. 그 중간을 임시로 랜선의 길이로 지정하여 계산한다.
• 최대값은 입력받은 영식이의 랜선의 길이 중 최대값으로 지정한다. 

 long left = 1;
 long right = max;
 
 //랜선 길이
long mid = (left + right)/2;

 

• 랜선의 길이를 지정하고 영식이의 랜선들로 만들 수 있는 랜선의 최대 개수를 구한다. 
• 만들어진 랜선의 개수가 필요한 (n) 개수 보다 작으면 랜선의 길이를 더 작게 하여 더 많은 랜선을 만들 수 있도록 범위의 최대값을 줄인다.
• 만달어진 랜선의 개수가 필요한 (n) 개수 보다 많으면 랜선의 길이를 더 길게 하여 랜선의 개수를 줄인다. 

while(left<=right)
{
   //랜선 길이
   long mid = (left + right)/2;

   long cnt = 0;

   for(long l : lanCable)
   {
        cnt += l/mid;
   }

   //만들 수 있는 랜선 개수 
   if(cnt < n) //랜선의 길이를 더 작게 하여 더 많은 랜선을 만들어야 한다.
   {
        right = mid-1;                   
   }
   else //랜선의 길이를 더 길게 하여 랜선의 개수를 줄인다.
   {
        left = mid+1;
        result = mid;
   }
}

 

---

🌕 최종코드

import java.io.*;
import java.util.*;
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 = Integer.parseInt(st.nextToken());

      //필요한 랜선 개수
      int n = Integer.parseInt(st.nextToken());          

      long[] lanCable = new long[k];

      long max = 0;

      for(int i=0;i<k;i++)
      {
           lanCable[i] = Integer.parseInt(br.readLine());
           max = Math.max(max,lanCable[i]);
      }          

      max++; // 가장 긴 랜선이 최대 길이가 될 수 있으므로 +1

      //랜선 만들기
      long left = 1;
      long right = max;
      long result =0;

      while(left<=right)
      {
           //랜선 길이
           long mid = (left + right)/2;

           long cnt = 0;

           for(long l : lanCable)
           {
                cnt += l/mid;
           }

           //만들 수 있는 랜선 개수 
           if(cnt < n) //랜선의 길이를 더 작게 하여 더 많은 랜선을 만들어야 한다.
           {
                right = mid-1;                   
           }
           else //랜선의 길이를 더 길게 하여 랜선의 개수를 줄인다.
           {
                left = mid+1;
                result = mid;
           }
      }

      System.out.println(result);
 }
}