99클럽 코테 스터디 11일차 TIL + 이분 탐색

백준

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

1654번: 랜선 자르기

 

---

- 오늘의 학습 키워드 : 이분 탐색

- 공부한 내용 본인의 언어로 정리하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

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()); // 필요한 랜선의 개수
    int[] lans = new int[K];

    long max = 0;

    for (int i=0; i<K; i++) {
      lans[i] = Integer.parseInt(br.readLine()); // 초기값 세팅
      if (max < lans[i]) max = lans[i]; // 최댓값 갱신
    }

    // 최댓값은 {1,1}인 경우를 위해 +1를 한다.
    max++;

    long min = 0; // 최솟값 정의
    long mid = 0; // 중간값 정의

    while (min < max) {
      mid = (min + max) / 2; // 범위 내 중간값
      long count = 0; // 랜선 개수

      for (int i=0; i< lans.length; i++) {
        count += (lans[i] / mid); // 만들 수 있는 랜선 개수
      }

      if (count < N) max = mid; // 필요한 랜선 개수보다 적으면 (min ~ mid)중에서 다시 이분 탐색을 한다.
      else min = mid + 1; // 필요한 랜선 개수보다 동일하거나 많으면 (mid+1 ~ max) 중에서 다시 이분 탐색을 한다.
    } // min이 max보다 큰 값으로 루프 종료

    System.out.println(min - 1); // 최종 값
  }
}

- 오늘의 회고 : 이분 탐색을 진행할 때는 max = mid / min = mid + 1 값 하기!

---

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽-1기 모집 중