[JAVA]BOJ 1654, 랜선 자르기

앞서 한 나무자르기와 비슷한 문제이다. 이진탐색을 이용했고 나무자르기처럼 답이 딱 안 떨어질 때가 있다. 여유있게 잘라줘야한다.(예: 1 3 / 4 인 경우.. 원하는 답은 3 -> 2로 자르면 2개나오고 1로 자르면 4가 나옴, 답은 1)

 

1. 입력 받고 정렬

2. 이진탐색을 이용해 특정값으로 잘라서 몇 개 나오는지 확인하기

3. 출력

 

1. 3. 은 생략

 

2. 이진탐색을 이용해 특정값으로 잘라서 몇 개 나오는지 확인하기

처음 이진탐색 범위는 1~제일 긴 랜선 길이(Lan[K-1])이다. 1개 이상은 나와야 몇개가 나오는지 셀 수 있기 때문이다.. 문제에서 준 예제는 4 11 / 802 743 457 539 이고, 제일 긴 랜선은 802이므로 1 ~ 802로 이진탐색을 한다. 이진탐색의 조건은 mid로 잘랐을때 랜선의 개수를 목표개수(N)와 비교하는 것이다. 여기까지는 쉽다.. 제일 어려운건 N의 최댓값을 구하는 것이다.

 

다시 4 11 / 802 743 457 539  로 예를 들면.. 우선 이 문제의 답은 200이다. 1 ~ 802로 랜선을 잘랐을때 값을 상상해보자. 

 

1 2 3   ....197 198 199 200 201 202 ..... 802

(생략)  ...  11   11   11   11   10   10 .......   1

 

이렇게 될것이다. 그리고 코드를 실행했을때 나오는 low, high, mid 는 아래와 같다.

2번째에 mid = 200, LANcount = 11 으로 정답이 나왔지만, 코드는 계속 돌아간다. 종료조건이 if(low > high)이기 때문이다. 2번째 턴에서 LANcount = 11 이 나왔지만 최댓값인지 확신할 수 없고, 201~400에 LANcount = 11인 경우가 있는지 더 확인해야한다.

public static long binarySearchRecursion(int[] LANcables, long low, long high, int N) {
    long mid;
    long LANcount;

    if(low > high) // 종료조건
        return high;
    else{
        mid = (high + low)  / 2;
        LANcount = getLANcount(LANcables, mid); // 잘라서 몇개 나오는지 확인하기
        if (LANcount >= N)
            return binarySearchRecursion(LANcables, mid + 1, high, N);
        else
            return binarySearchRecursion(LANcables,low, mid - 1, N);
    }
}

 

그래서 위 처럼 if(LAN >= N) {..생략} 인 조건이 들어간다.

N과 LANcount가 일치하지 않을때도 가능하다. 앞의 나무자르기처럼 LAN == N으로 조건을 맞춘게 아니기 때문에..

N과 LANcount가 일치하지 않을때 예시, 5개가 필요한데 6개까지 자름

---

아래는 전체 코드이다.

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

public class BOJ1654 {
    public static int getLANcount(int[] LANcables, long LANlength){ // 이 함수를 실행한다는 것은 LANlength가 int범위임을 뜻함
        int i, cnt = 0;

        for(i=0;i<LANcables.length;i++){
            cnt += LANcables[i] / (int)LANlength;
        }
        return cnt;
    }

    public static long binarySearchRecursion(int[] LANcables, long low, long high, int N) {
        long mid;
        long LANcount;

        if(low > high)
            return high;
        else{
            mid = (high + low)  / 2;
            LANcount = getLANcount(LANcables, mid); // 잘라서 몇개 나오는지 확인하기
            // 출력 예시
		// System.out.println("low : " + low + " , high : " + high + " , mid : " + mid);
		// System.out.println("LANcount : "+LANcount);

            if (LANcount >= N)
                return binarySearchRecursion(LANcables, mid + 1, high, N);
            else
                return binarySearchRecursion(LANcables,low, mid - 1, N);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K, N, i;
        StringTokenizer st = new StringTokenizer(br.readLine());

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        int[] LANcables = new int[K];

        for (i = 0; i < K; i++)
            LANcables[i] = Integer.parseInt(br.readLine());

        //정렬
        Arrays.sort(LANcables);

        System.out.println(binarySearchRecursion(LANcables, 1, LANcables[K-1], N));
    }
}