[백준] 1654번 - 랜선 자르기 (Java)(○)

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

1654번: 랜선 자르기

 

<문제 분석>

K개의 길이가 다른 랜선을 가지고 있다.

이를 잘라서 같은 길이의 N개의 랜선을 만들어야 한다.

N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. ( <= N)

 

<풀이>

1. 완전탐색으로 풀면 시간 초과가 발생하니 이분탐색으로 풀자.

2. 오름차순으로 정렬한 후 가장 작은 수를 기준으로 이분 탐색을 한다.

  2-1. mid값으로 랜선을 나눠서 개수가 N이 되는지 확인한다.

  2-2. 만들어진 수가 <N이면 길이가 크다는 것이므로 end = mid -1을 한다.

3. N개 보다 많이 만드는 것도 성립하기 때문에 타겟과 같은 수 혹은 큰 값이 처음 나오는 지점을 찾는 Lower Bound 알고리즘을 이용하자.

 

<코드 구현>

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

/*
[백준] 1654번 - 랜선 자르기 (Java)
*/

public class Main {
    static int K;
    static long N;    
    static long A[];
    
    void InputData() {
        Scanner in = new Scanner(System.in);
        K = in.nextInt();
        N = in.nextLong();
        A = new long[K];
        for (int i=0; i<K; i++) {
            A[i] = in.nextLong();
        }
    }
    
    // key 보다 크거나 같은 첫번째 위치 반환
    long lowerBound(long start, long end, long key) {
        long ans = 0;
        while (start <= end) {
            long mid = (start+end)/2;
            long count = countCable(mid);
            if (count >= key) { // 랜선 개수가 key보다 같거나 많으면
                start = mid+1; // 선길이를 +1씩 늘려봄
                // mid 최대값을 계속 저장해야함.
                ans = Math.max(ans, mid);    
            } else { // 랜선 개수가 key보다 작으면
                end = mid; // 선길이를 -1 씩 줄여봄
                
            }
            //System.out.println("-> s= "+start+", e= "+end+", ans= "+ans);            
        }
        return ans;
    }

    long countCable(long mid) {
        long sum = 0;
        for (int i=0; i<K; i++) {
            sum += A[i]/mid;
        }
        //System.out.println("mid= "+mid+", sum= "+sum);
        return sum;
    }
 
    void Solve() {
        Arrays.sort(A);
        long ans = lowerBound(1, A[K-1], N);
        System.out.println(ans);
    }

	public static void main(String[] args) {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<수정점>

1. 이분탐색에 사용되는 정수형 변수들을 모두 long 타입으로 바꿨다.

2. (반례) 2개의 랜선이 있고 모두 길이가 1이면 min = 0, max = 1이 된다.

mid = (0 + 1)/2가 되므로 mid는 0이 된다. 실제로 반환되어야 하는 upper bound값은 1이 되어야 한다.

따라서, 자연수 탐색 범위를 0 ~ max가 아닌 0 ~ max+1을 해줘야 한다.

 

<수정 코드>

import java.util.Scanner;
import java.io.IOException;
import java.util.Arrays;
import java.lang.Math;

//[백준] 1654번 - 랜선 자르기 (Java)

public class Main {
    static int N, K;
    static long max=0;
    static int A[];
    
	public void InputData() throws IOException
	{
        Scanner sc = new Scanner(System.in);
        K = sc.nextInt();
        N = sc.nextInt();
        A = new int[K];
        for (int i=0; i<K; i++) {
            A[i] = sc.nextInt();
            max = Math.max(max, A[i]);
        }
	}

    public long UpperBound(long start, long end, int key) {
        while (start < end) {
            long mid = (start+end)/2;

            int count = 0;
            for (int x : A) {
                count += x/mid;
            }
            // 원래 중간 위치의 값이 키 값보다 작으면 상한선을 올려야 한다.
            // 하지만 mid를 증가시키면 count는 감소하는 형태이기 때문에 일반적인 upper bound와 반대로 구현해야 한다.
            
            if (count < key) { // count값을 증가시키려면 mid값이 작아져야 한다.
                end = mid; // 상한선을 감소
            } else { // key <= count
                start = mid + 1; // 하한선을 증가
            } 
        }
        return end;
    }
	public void Solve() {
        long ans = UpperBound(0, max+1, N);
        System.out.println(ans-1);

	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<풀이 #2>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    static int K;
    static long N;
    static long A[];

    // key는 필요한 랜선의 개수
    // key 보다 크거나 같은 첫번째 위치 반환
    long lowerBound(long start, long end, long key) {
        long lb = 0;
        while (start <= end) {
            long mid = (start+end)/2;
            long count = countCable(mid);
            if (count >= key) { // 랜선 개수가 key보다 같거나 많으면
                lb = mid; // 일단 현 mid값은 lb에 저장함.
                start = mid+1; // 선길이를 +1씩 늘려서 랜선 개수가 더 줄어들지 않는지 확인한다  
            } else { // 랜선 개수가 key보다 작으면
                end = mid-1; // 선길이를 -1 씩 줄여서 갯수가 더 늘어가는지 본다
            }          
        }
        return lb;
    }

    // mid값으로 나눠서 나오는 케이블 개수를 구하는 함수
    long countCable(long mid) {
        long sum = 0;
        for (int i=0; i<K; i++) {
            sum += A[i]/mid;
        }
        return sum;
    }

	void Solve() {
        Arrays.sort(A);
        long ans = lowerBound(1, A[K-1], N);
        System.out.println(ans);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());//열
        N = Integer.parseInt(st.nextToken());//행
        A = new long[K];
        for (int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            A[i] = Long.parseLong(st.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}