[Java] BOJ 1654 랜선 자르기

문제 

문제 링크 https://www.acmicpc.net/problem/1654

• 오영식은 자체적으로 K개의 랜선을 가지고 있다.
• 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.
• 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
• 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자.
• 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
• 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
• 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다.
• K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다.
• 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.
• 첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

아이디어

• 이분탐색을 활용해서 풀었다.
• 랜선 길이를 입력받으면서 찾은 최댓값을 가지고 이분탐색을 했는데 시작점은 1, 끝점은 최댓값으로 이분탐색을 했다.
• 시작점과 끝점을 더해서 2를 나눈 값으로 랜선들을 나눴을 때, 나온 몫들을 더한 값이 필요한 랜선 개수보다 작다면 랜선길이가 더  짧아야되므로 시작점을 1로 끝점을 (시작점 + 끝점) / 2 - 1로 잡고 다시 이분탐색을 돌렸다.
• 만약 필요한 랜선 개수보다 같거나 크다면 랜선 길이를 (시작점 + 끝점) / 2 로 갱신해준다.
• 그리고 랜선 길이가 더 길어도되므로 시작점을 (시작점 + 끝점) / 2 + 1로 잡고 끝점을 최댓값으로 잡고 다시 이분탐색을 돌렸다.
• 계속 이분탐색을 돌리다가 끝점이 시작점보다 길어질 경우, 함수를 종료했다. 

겪은 시행착오

• 많이도 틀렸다... 처음에는 정말 쉽게 생각하고 최솟값을 찾아서 거기서 1씩 빼면서 그 값으로 랜선들을 나눈 몫들을 더했을 때 필요한 랜선 개수보다 같거나 크다면 반복문을 멈추는 방식으로 풀었다. 
• 그런데 내가 하나 간과한 사실이 있었다... 모든 랜선을 쓸 필요가 없다는 뜻이였다... 
• 그 후로 최솟값을 최댓값으로 바꾸고 풀었지만 시간초과가 나왔고 이분 탐색으로 풀게 되었다.
• 그 뒤에도 많이...도.. 틀렸는데... 이분탐색 방법이 완전하지 않아 많은 시행착오를 겪은 과정이다... ㅎㅎ 
• 그 외에도 탐색 범위를 의미하는 변수들은 long타입을 써줘야했었는데 int를 썼었다... ㅜㅜ (1 + (2^31-1) 에서 오버플로가 발생하기 때문이다...)
• 그래도 수많은 시행착오들 후에 문제를 푸니까 뿌듯했다...!

ㅎㅎㅎ... 오늘 문제들... 힘들다...

힘든 싸움이였다.... 그래도 덕분에 이분탐색 방법은 확실히 알게된 것 같다...ㅎㅎ

코드

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

public class BOJ1654 {
    static long max;
    static long result;
    static int K;
    static int N;
    static int lans[];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 가지고 있는 랜선 개수
        K = Integer.parseInt(st.nextToken());
        // 필요한 랜선 개수
        N = Integer.parseInt(st.nextToken());

        // 랜선 저장 배열
        lans = new int[K];

        // 최댓값을 저장할 변수
        max = Integer.MIN_VALUE;

        for(int i = 0; i < K; i++){
            int l = Integer.parseInt(br.readLine());

            // 배열에 저장
            lans[i] = l;

            // 최댓값이 입력받은 수보다 크다면
            // 입력받은 수를 최솟값으로 갱신
            if(l > max){
                max = l;
            }
        }

        // 결과값을 저장할 변수
        result = 0;

        cutting(1, max);

        System.out.println(result);
    }

    // 랜선 자르는 함수
    public static void cutting(long s, long l){
        // 시작점이 끝점보다 더 커진다면 종료
        if(l - s < 0){
            return;
        }

        // 랜선의 길이를 (시작점 + 끝점)/2를 해줌
        long len = (s + l) / 2;

        // 자른 랜선의 개수
        long cnt = 0;

        // 반복문을 통해 랜선들을 잘라서 몇개 나오는지 더함
        for(int j = 0; j < K; j++){
            cnt = cnt + (lans[j] / len);
        }

        // 만약 자른 랜선들의 개수가 필요한 랜선 개수보다 크거나 같다면
        if(cnt >= N){
            // 중간값과 끝점을 기준으로 다시 함수를 돌림
            result = len;
            cutting(len + 1, l);
        }
        // 만약 개수가 작다면 랜선의 길이가 더 작아야된다는 뜻이므로
        else{
            // 시작점과 중간점을 기준으로 다시 함수를 돌림
            cutting(s, len - 1);
        }
    }
}