Baekjoon 문제 풀기 (1654번 : 랜선 자르기) Java

1654번 : 랜선 자르기

1. 문제읽기

---

이진탐색 알고리즘의 대표적인 문제(라고한다)

일반적인 이진탐색 문제이다.

2. 제출 코드

---

두 가지 정도의 함정이 숨어있는 문제..

1. 랜선 길이의 시작 값이 0이면 안된다.
   사실 문제에서 이미 1이상이라고 정해줬기 때문에 큰 함정은 아니었다.
   그런데 초기화 시킨다고 0으로 하게되면 start가 0 이고 end가 1일 때, mid가 0이 되므로 0으로 나누는 코드가 생기면서 에러가 발생한다.
2. 자료형
   문제에서 랜선의 길이는 $2^{31}-1$ 보다 작거나 같은 자연수라고 했으므로 최솟값이 1, 최댓값이 $2^{31}-1$이라면 더하면 $2^{31}$이 되므로 int 자료형의 최댓값을 넘어가버린다. (int 자료형의 최댓값은 $2^{31}-1$)
   따라서 start, end, mid는 long형으로 선언해주어야한다. (count는 int형 가능)
   사실 맨 마지막 랜선의 길이 조건은 보지 못했다.(변명.. 문제를 잘 확인하자)

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

public class BOJ1654 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        List<Integer> arr = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            arr.add(Integer.parseInt(bf.readLine()));
        }
        long max = 0;
        for(int i : arr) {
            if(max < i) {
                max = i;
            }
        }
        long start = 1;
        long end = max;
        while(start <= end) {
            long count = 0;
            long mid = (start+end)/2;
            for(int i : arr) {  // 랜선 잘라 갯수 구하기
                count += i/mid;
            }
            if(count >= n) {  // 갯수를 충족할 때, 최대 길이인지 확인
                start = mid+1;
            } else {  // 갯수가 작으면 기준을 내림
                end = mid-1;
            }
        }
        System.out.println(end);
    }
}

3. 공부할 것

---

문제 조건 잘보기!!