[알고리즘] 백준 1654 렌선 자르기 Java 문제 풀이

랜선 자르기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

262377

63594

42917

21.821%

문제

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

이미 오영식은 자체적으로 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줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

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

 

예제 입력 1 

4 11
802
743
457
539

 

예제 출력 1 

200

 

힌트

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

출처

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: djm03178, peter5264, plzrun, skydreamer21, twicedtna
• 문제의 오타를 찾은 사람: helloworld123
• 빠진 조건을 찾은 사람: iriszero

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

반응형

풀이 코드

이 문제는 이진 탐색으로도 풀수는 있지만 Parameter metric(매개 변수)를 이용해 문제를 풀이한 코드이다.

Parameter metric은 매개 변수를 함수의 입력으로 넣고 필요한 값을 추출하여 이진 트리 방식으로 탐색을 하는 방식이다.

 

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

public class Solution{
	
		static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		static StringTokenizer st;
		static int K;
		static int N;
		
		
		static int callength(long[] len, long middle) {
			int cnt =0;
			for(long lan :len) {
				cnt += lan/middle;
			}
			return cnt;
		}
	    public static void main (String[] args) throws IOException {
	    	st = new StringTokenizer(br.readLine());
	    	//현재 가지고 있는 랜선의 수
	    	K = Integer.parseInt(st.nextToken());
	    	
	    	//필요한 렌선의 갯수 
	    	N = Integer.parseInt(st.nextToken());
	    	
	    	long[] len = new long[K];
	    	
	    	for(int i=0; i < K; i++) {
	    		st = new StringTokenizer(br.readLine());
	    		len[i] = Long.parseLong(st.nextToken());
	    	}
	    	
	    	long start =1;
	    	long end = (1 << 31) -1;
	    	long ans =0;
	    	while( start <= end) {
	    		long middle = (start + end) /2;
	    		if(callength(len, middle) >= N) {
	    			start = middle +1;
	    			ans = middle;
	    		}
	    		else end = middle -1;
	    	}
	    	bw.write(ans+ "\n");
	    	bw.flush();
	    }
	}