1654번 - 랜선 자르기

(문제 출처)

• 난이도 : 실버 3(solved.ac 기준)
• 언어 : java

• 문제 요약

  N개의 랜선을 일정 길이 만큼 잘라서 K개 이상이 나오는 최대 길이를 구하라.
  (단, 이미 자른 랜선은 붙일 수 없다.)

• 유의 사항
  입력 조건 중 랜선의 길이가 int형의 최대 범위인 2³¹-1까지다.
  2개 이상의 랜선 중 하나라도 2³¹-1의 값이 입력되도 랜선을 1cm씩 자른다면
  랜선의 개수 카운팅을 할 때 int형의 최대 범위를 초과해버리니
  랜선 개수 변수를 최소 long형을 사용하여야 한다.

  • 예시

    2³¹-1, 1이 입력 됐을 경우 1cm 길이로 자를 경우
    랜선의 개수는 2³¹-1 + 1 = 2³¹개가 된다.

• 문제 풀이
  이 문제는 이진 탐색(Binary Search)를 사용해야 한다.
  시간 제한이 2초이기 때문에 순차 탐색을 하면 시간 초과가 난다.

  순차 탐색은 최악의 경우 시간 복잡도가 n이지만 이진 탐색은 log n이다.

  • 탐색 조건
    각 리스트의 값과 중간 값을 나눈 값의 몫을 카운팅하여 더한 값을 이용하여야 한다.
    • 카운트가 필요 갯수보다 적을 경우 자를 랜선의 길이를 줄여야 하고
    • 반대로 갯수가 많을 경우 자를 랜선의 길이를 늘려야 한다.
    • 갯수가 일치해도 이상의 값을 허용하므로 최대 길이를 구하기 위해
      자를 랜선이 길이를 늘려야 한다.

• 코드

  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 39 40 41

  import java.io.*; public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); try { String[] input = br.readLine().split(" "); int K = Integer.parseInt(input[0]); int N = Integer.parseInt(input[1]); int haveMax = 0; long maxHeight = 0; int[] lan_List = new int[K]; for (int i = 0; i < K; i++) { lan_List[i] = Integer.parseInt(br.readLine()); haveMax = Math.max(lan_List[i], haveMax); } long mid, left = 1, right = haveMax; long cnt = 0; while (right >= left) { mid = (right + left) / 2; for (int j = 0; j < K; j++) { cnt += lan_List[j] / mid; } if (cnt >= N) { // 필요한 수량보다 같거나 더 많을 경우 maxHeight = Math.max(mid, maxHeight); left = mid + 1; } else { // 필요한 수량보다 더 적을 경우 right = mid - 1; } cnt = 0; } bw.write(maxHeight + "\n"); bw.flush(); bw.close(); br.close(); } catch (Exception e) { System.out.println(e.getMessage()); } } }

• 후기
  이진탐색에 대해 개념은 알고 있었지만 실제로 코드 짜는 것은 처음이어서 좋은 경험이 됐다.
  처음에 int형 범위를 초과할 줄 몰랐다. 질문 게시판에 들어가서야 알게 됐다.
  후에 새로운 테스트 값으로 디버깅 과정에서 눈으로 직접 확인했다.
  이진 탐색 조건 잡는 데 생각보다 애를 먹었다.