[Java] baekjoon_1654 : 랜선 자르기

이분 탐색 (이진 탐색)

랜선 자르기 : Silver2

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

1654번: 랜선 자르기

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    ArrayList<Integer> al = new ArrayList<>();
    
    for (int i = 0; i < n; i++) {
      al.add(Integer.parseInt(br.readLine()));
    }
    // 이진 탐색(이분 탐색)을 위한 초기값 설정
    long start = 1;
    long end = Collections.max(al);

    // 이진 탐색(이분 탐색) 시작
    while (start <= end) {
      long mid = (start + end) / 2;
      long cnt = 0;

      // mid 길이로 잘랐을 때 얻을 수 있는 랜선의 개수 계산
      for (int i = 0; i < n; i++) {
          cnt += al.get(i) / mid;
      }

      // 얻은 랜선의 개수가 목표 개수보다 크거나 같으면 길이를 늘림
      if (cnt >= m) {
          start = mid + 1;
      } else {
          // 목표 개수보다 작으면 길이를 줄임
          end = mid - 1;
      }
    }

    // 최대 길이 출력
    bw.write(String.valueOf(end));
    bw.newLine();
    bw.flush();
    bw.close();
  }
}

 

 

 

이진 탐색(이분 탐색)

https://velog.velcdn.com/images/ming/post/ab848f15-3998-4e61-b061-01458ad6f18d/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89.png

• 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

 

---

 

 

문제점 : 이진 탐색(이분 탐색) 알고리즘에 대해 알지 못한 상태로 문제를 풀어서 IDE를 이용해서 디버깅 했을 때는 결과값이 옳게 출력되었지만 백준 제출 시 런타임 에러가 발생하였다.

해결 방법 : 이진 탐색(이분 탐색) 알고리즘을 서치하여 공부하였다.

깨달은 바 : 런타임 에러 발생 시 아예 다른 방법을 찾아보는 것이 좋은 것 같다.