[백준] 1654 - 랜선 자르기 JAVA 재귀함수를 이용한 이진탐색

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

 

---

링크

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

1654번: 랜선 자르기

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 300cm짜리 랜선에서 140cm 140cm짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,00010,000 이하의 정수이고, N은 11 이상 1,000,0001,000,000 이하의 정수이다. 그리고 항상 K ≦N이다. 그 후 KK 줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

 

접근방법

K개의 랜선을 야무지게 잘라서, 가지런히 놓았을 때 그 개수가 N개가 되도록 만드는 것을 문제가 요구하고 있다. 우리가 생각해야 할 것은 크게 두 가지이다.

 

• K개의 랜선을 야무진 길이로 자르기 위해, 어떻게 길이를 조절할 것인가  
• 어떻게 나뉜 랜선의 개수를 구할 것인가.

문제에서 제시한 범위가 작지 않다.(엄청 크다) 단위를 잡고 하나씩 잘라보고, 그것으로 자른 랜선들의 개수를 세야 하는데, 선형 탐색(순차 접근)이라면 상수 시간이 걸리기 때문에 시간 초과에 걸릴 확률이 높다.

 그렇기에 이번 문제에서는 이진 탐색 알고리즘을 사용해서 탐색 시간을 줄일 것이다. 이진 탐색에 대한 이론이 필요하다면 정리한 글을 참고하자. 

 

 

[알고리즘] 이진 탐색(Binary Search) - 장점과 복잡도

 여기까지 생각하면서 확실한 점이 한 가지 생겼다. 해당 문제는 우리에게 이진 탐색에 대한 이해와 풀이 능력을 묻고 있다는 것이다. 이 정도 생각을 잡고 풀이에 들어가자. 혹시 아직 혼자 해내고 싶은 마음이 있다면, 접은 글에 내가 실패했던 흔적을 적어 놓았으니, 피드백하는 것도 좋을 것 같다.

실패 원인

 나 역시도 엄청 많이 틀렸다. 혹시 나와 같이 연속된 실패에 직면하였다면, 정신을 환기시키고, 다시 풀이에 임하자. 정신을 쉬게 하고 풀었더니, 매달릴 때 보다 나았다. 나처럼 5 연속 실패에 해답이 궁금해서 블로그를 찾은 거라면, 오늘은 보면서 이해하고, 다음날 혼자 다시 푸는 것을 추천한다. 

내가 실패한 이유는 '어떻게 최대 길이를 판단할 것인가?'에 대한 부분을 간과했다. 또한 이 문제의 가장 큰 함정은 특정 크기로 잘랐을 때, N보다 많이 나와도 그 길이가 최대 값이 될 수 있다는 것이다. (이 부분이 문제를 어렵게 만드는 것 같다.)

예제를 보자. 아래 예제는 joey09 님의 포스팅에서 가져온 잘 틀리는 반례들이다.

 

예제 1) 자른 개수가 N보다 더 큰 경우

2 3

3

2

output : 1

-> 동일한 크기로 자르면, 자른 개수가 N보다 큰 경우

해당 예제의 답은 1이다. 1로 자르면 총 5개의 랜선이 나오는데 이는 N 보다 크다. 이 예제가 의미하는 것은 N보다 작은 개수는 문제가 되지만, 큰 것은 문제가 안 되는 열린 범위라는 것이다. 나는 이것이 이 문제에 가장 어려웠던 문제였다. 너무 작게 잘라 N 보다 자른 개수가 크면, 이진 탐색에 인해 탐색 범위가 재조정되는데, 재조정된 범위가 N보다 작게 된다면, 그 이전에 구한 값을 최대로 선택하여 리턴을 보내줘야 하기 때문이다. (이것에 대한 해답은 풀이에 있다.)

 

그 외에도 몇 가지 반례가 추가로 더 있다. 참고하면 좋을 것 같다.

 

예제 2) 랜선이 한 개라 자를 수 없는 경우

1 1

2147483647

output : 2147483647

예제 3) 더 이상 쪼갤 수 없는 경우

5 5

1

1

1

1

1

output : 1

예제 4) 특정 랜선에서만 잘리는 경우

3 6

40

20

1

output : 10

아웃풋이 잘 나오는지 확인해 보자

 

 

풀이

 문제를 쪼개서 정복하자.(divide & conquer) 우리에게 필요한 것은 1) k를 자르는 적당한 수를 찾는 것 2) 그것으로 자른 랜선의 개수를 구하는 법이다. 

 

 

자른 랜선의 개수를 구하는 함수부터 만들었다. (가장 쉬운 것부터 하자.)

그리고 적당히 수를 찾으려니, 순차 탐색은 너무나도 시간 소요가 컸다. 때문에 이진 탐색을 생각했다. 이진 탐색을 위해서는 반드시 정렬이 우선되어야 하므로, 정렬부터 시작했다. 

 

 

 이제 이진 탐색에 대한 로직만 만들면 끝난다. 우선, 반환 값은 자를 수 있는 최대 길이로 정했다. 그 후 이진 탐색에 필요한 start와 end, 확인할 데이터를 파라미터에 넣고 로직을 짰다. 여기서 마주친 문제는 N 이상을 만족하는 최대의 길이를 어떻게 리턴해야 하는 것이었다. 머리가 안 돌아가서 다시 정리를 해봤다. 문제에서 요구하는 최대길이를 말로 풀면 대충 이런 말이 된다.

 

"N 이상 쪼개지는 건 상관없어. 근데 그게 만들 수 있는 최대 길이 어야 해. 그게 아니라면, 그냥 이전 길이를 줘"

 

이 말을 재해석하면, N 이상을 만족하는 길이라도, 최댓값이 아니면 예전 값을 리턴해 달라는 의미이다. 

그렇기에 이전 값을 버리면 안 된다. 저장해 두고, 반환 값과 비교해서 큰 값을 반환할 수 있게 반환 값을 조정했다.

그리고 성공했다.

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main test =new Main();
    }

    public Main() throws IOException {
        //입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] info = br.readLine().split(" ");
        int length = Integer.parseInt(info[0]);
        int target_cnt = Integer.parseInt(info[1]);

        long[] data = new long[length];

        for (int i = 0; i < length; i++) {
            data[i] = Integer.parseInt(br.readLine());
        }

        //이진 탐색을 위한 정렬
        Arrays.sort(data);

        //탐색
        int result = binary_search(1, data[length - 1], 0, target_cnt, data);

        System.out.println(result);
       
    }

    //이진 탐색

    /**
     * @param start      start 이진 탐색 시작변수
     * @param end        end 이진 탐색 마지막 변수
     * @param result     result 이진 탐색을 통해 나온 길이
     * @param target_cnt 목표로 하는 랜선 갯수
     * @param data       원본데이터
     */
    public int binary_search(long start, long end, int result, int target_cnt, long[] data) {

        //재귀 종결 조건 (start 지점과 end가 역전되는경우
        if (start > end) {
            return result;
        }

        //중간 지점
        long mid = (long) Math.floor((start + end) / 2);

        //중간 지점을 기준으로 갯수 확인
        int count = check_count(data, mid);


        //count 갯수가 적다 --> mid가 크다 --> 길이를 줄여야한다 --> end 수정
        if (count < target_cnt) {
            end = mid - 1;
        } else {
            //count 갯수가 크다 --> mid가 작다
            // --> target_cnt는 일단 만족한다
            // --> 그러나 최대인지 알 수 없으므로 길이를 늘려야함 --> start 수정
            start = mid + 1;
            result = (int) mid;
        }

        //start 혹은 end를 수정해서 재귀
        int next_result = binary_search(start, end, result, target_cnt, data);

        //새로 구한 랜선의 길이가 이전 길이보다 작다면 결과값을 바꿔줄 필요가 있다.
        if (next_result < result) {
            next_result = result;
        }
        return next_result;
    }

    // div를 기준으로 나눴을 때, 나오는 랜선의 수
    public int check_count(long[] data, long div){
        boolean answer = true;
        int cnt = 0;
        for (long num : data){
            cnt+=(int)(num/div);
        }

        return cnt;
    }

}

 

 

 

결과

구글에 반복문을 통해 작성한 코드들이 많은데, 재귀 함수로 구현한 것은 하나도 없는 것 같아서 비교해보았다.

32412366  : 메서드 분리, 재귀 함수를 통한 이분 탐색

32396472 , 32396303 : 코드 통합, 반복문을 이용한 이분 탐색

 

재귀가 더 빨랐는데, 큰 차이는 없는 것으로 보인다.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다. 

 

 

 

반례 출처: https://joey09.tistory.com/115