[백준] 1654번 랜선 자르기(JAVA)

문제

- 길이가 제각각인 K개의 랜선으로 같은 길이의 N개의 랜선을 만들어야 함

- 이미 자른 랜선은 붙일 수 없고 버려야 함

- 랜선을 자르거나 만들 때 손실되는 길이는 없음

- 기존 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없음

- 항상 정수 길이만큼 자름

- N개보다 많이 만드는 것도 N개를 만드는 것에 포함

- K는 1 이상 10,000 이하의 정수

- N은 1 이상 1,000,000 이하의 정수

- 항상 K <= N

- 랜선의 길이는 2^31-1보다 작거나 같은 자연수

 

고찰

처음에 코드를 짤 때에는 정수 범위에서 넘칠 것을 생각하지 못하고 min, max, mid 값을 int로 설정하여 코드를 작성하였다. 하지만, 가장 긴 길이의 랜선이 2^31-1cm이라면, min값은 1이상이여야하기 때문에 mid를 구하는 과정에서 오버플로우가 발생하여 제대로 된 답을 구할 수 없게 된다. 따라서 처음에 작성한 코드로 제출 했을 때 틀렸습니다.를 볼 수 있었다. 

테스트케이스는 맞았었기 때문에 어떤 부분에서 틀렸는지 감을 잡지 못했었고, 구글링을 통해 자료형 설정에 오류가 있었음을 확인할 수 있었다. 항상 이렇게 범위를 생각 못하고 코드를 막 짜고 구글링을 통해 문제를 발견하면 너무 허무한 것 같다..

처음 코드를 설계할 때부터 이러한 부분을 꼼꼼하게 파악하고 코드 짜는 연습을 더 해야할 것 같다.

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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;				// 랜선 길이의 최대값
        long min = 1;				// 랜선 길이의 최소값 : 랜선의 길이는 자연수기 때문에 1로 설정
        long mid = 0;				// 랜선 길이의 중간값

	// 랜선 길이 입력받기
        for(int i = 0; i<K; i++){
            lans[i] = Integer.parseInt(br.readLine());
            if(max < lans[i]){
                max = lans[i];
            }
        }
		
        // 이분탐색
        while(max>=min){
            mid = (max + min) / 2;	// 중간 길이 계산
            long count = 0;		// 자른 랜선의 개수

	    // 랜선 자르기
            for(int i = 0; i<K; i++){
                count += lans[i] / mid;
            }

            if(count>=N){
            	// 더 많은 랜선이 나온 경우에는 길이를 더 크게 하여 잘라주어야 함
                min = mid+1;
            }else{
            	// 개수가 적으면 길이를 작게하여 더 많이 자를 수 있도록 해야 함
                max = mid-1;
            }
        }

        System.out.println(max);

        br.close();
    }
}