[JAVA] 백준 1654 랜선 자르기

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

1654번: 랜선 자르기

 

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

 

- 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선을 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 

 

- 예를들어 300cm 짜리 랜선에서 140cm짜리 랜선을 두개 잘라내면 20cm는 버려야 한다. .

(이미 자른 랜선은 붙일 수 없다.)

 

- 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 

- 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정 

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

- 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램 

 

 

문제 풀이

 

매개 변수 탐색(Parametric Search)

 

매개변수 탐색 (Parametric Search) (velog.io)

매개변수 탐색 (Parametric Search)

 

[C++ Algorithm] 매개 변수 탐색(Parametric Search) — while(true) { continue; } (tistory.com)

[C++ Algorithm] 매개 변수 탐색(Parametric Search)

- 이진 탐색(이분 탐색)을 사용하여 조건을 만족하는 최대값을 구하는 방법 

- 최적화 문제를 결정 문제로 바꿔서 푸는 방법

- 이진 탐색과 풀이 방식이 유사하며, 시간 복잡도는 log2(N)

 

매개변수 탐색을 사용하는 경우 

 

1) 특정 지점 이전에는 조건을 만족하지만 이후에는 조건을 만족하지 않는 경우 최댓값을 구할 때

2) 특정 지점 이전에는 조건을 만족하지 않지만 이후에는 조건을 만족하는 경우 최솟값을 구할 떄 

 

 

매개변수와 결정 함수 

 

매개변수 

 

- 찾고자 하는 최솟값 또는 최댓값이 존재하는 구간의 값

- 매개변수는 연속이어야 함 

 

결정 함수 

 

- 조건의 만족여부를 판정하는 함수 

- 문제에 제시된 조건에 따라 계산한 다음에 true 또는 false를 반환하여 조건의 만족여부를 알려줌

- 결정함수의 결과 또한 매개변수에 대해서 연속이어야 하며, 주어진 구간에 대해서 한 지점에서만 조건의 만족여부가 바뀌어야 한다. 

- 즉, 구간의 앞부분에서 만족하다가 뒷부분에서 만족하지 않거나, 구간의 앞부분에서 만족하지 않다가 뒷부분에서 만족해야 한다. 

 

문제의 매개변수 

- 최대 랜선의 길이 x

- x의 길이는 검사범위에서의 중간 값(mid)이고, 결정함수의 결과에 따라서 x를 늘리고 줄이면서 확인

- x의 범위 (1 ~ k개의 랜선들 제일 긴 길이)

 

문제의 결정 함수 

 

- "K개의 랜선을 각각 길이 x로 잘랐을 때, N개의 랜선을 만들 수 있어야 한다."로 설정

- 위의 조건을 만족하면 true를 , 만족하지 않으면 false를 반환 

 

- K개의 랜선을 각각 길이 x로 나눈 몫을 모두 더한다.

- 이 값이 n보다 크거나 같으면 조건을 만족하는 것이기 때문에 true를 반환하고, 이 값이 n보다 작으면 조건을 만족하지 못하기 때문에 false를 반환 

 

- true를 반환했다는 이야기는 랜선을 n개 이상 만들었다는 뜻이므로, 랜선의 길이 x를 좀 더 늘려봐도 된다. 

- 따라서 중간 값(mid)의 값을 더 높여야 한다. 그러므로 low = mid+1을 해준다. 

 

- false를 반환했다는 이야기는 랜선을 n개 미만 만들었다는 뜻이므로, 랜선의 길이 x를 줄여야 한다.

- 따라서 중간 값(mid)의 값을 더 낮춰야 한다. 그러므로 high = mid -1을 해준다. 

 

- 이런 방법으로 계속 진행하다가 low > high가 되는 순간, 즉 검사할 구간이 더 이상 남아있지 않는 경우 검사를 종료 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int lansun[];
    static long max, min, mid;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int K = Integer.parseInt(st.nextToken()); //이미 가지고 있는 랜선의 개수
        int N = Integer.parseInt(st.nextToken()); //필요한 랜선의 개수 
        
        lansun = new int[K];
        
        max = Long.MIN_VALUE;
        min = 0;
        
        for(int i=0; i<K; i++)
        {
        	st = new StringTokenizer(br.readLine());
            lansun[i] = Integer.parseInt(st.nextToken());
            max = Math.max(lansun[i],max);
        }
        max++;
        
        while(min<max)
        {
            mid = (min+max)/2;
            
            long cnt = 0;
            
            for(int i=0; i<K; i++)
            {
                cnt +=lansun[i]/mid; //각 랜선마다 몇 칸씩 나오는지 
            }
            
            if(cnt<N)
            {
                max = mid;
            }
            else
            {
                min = mid+1;
            }
        }
        
        bw.write(String.valueOf(min-1));
        
        bw.flush();
        bw.close();
        br.close();
    }
}