[Java+Python]1654번, 랜선 자르기

목차

이진 탐색

 

[Java+Python]1920번, 수 찾기

[Java+Python]1654번, 랜선 자르기

[Java+Python]2805번, 나무 자르기

[Java+Python]2110번, 공유기 설치

[Java+Python]2805번, K번째 수

[Java+Python]12015번, 가장 긴 증가하는 부분 수열 2

문제

 

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 

박성원이 캠프 때 쓸 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 줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 

랜선의 길이는 $2^{31}-1$보다 작거나 같은 자연수이다.

 

출력

 

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

 

풀이

 

주어진 랜선을 잘라서 N개 이상의 랜선을 만들 수 있는 최대 길이를 구하는 문제이다.

 

언뜻 생각하면 이진 탐색과 별 상관이 없어 보이는 문제이고, 아직 이진 탐색에 익숙하지 않은 탓인지

 

설계 자체가 오래 걸렸다. 역시 다른 사람의 풀이도 참고했고.

 

알고리즘의 진행 순서는 다음과 같다.

 

1. 입력으로 주어지는 k와 n을 저장하고, k개의 랜선을 저장할 배열(리스트) lengths를 선언하고 값을 넣어준다.
2. 배열(리스트)의 최댓값을 변수 max에 저장한다.
3. 탐색의 기준이 될 길이의 최솟값 left를 1로, right를 max로 설정한다.
4. 이진 탐색을 시작한다(left <= right 인 경우)
   
   
   1. left와 right의 중간인 mid를 계산하고, 만들어낸 랜선의 개수를 저장할 변수 count를 0으로 초기화한다.
   2. 각 랜선을 순회하며 mid 값으로 잘랐을 때의 랜선 개수를 count에 누적시켜 준다.
   3. 누적이 끝난 count의 값이 n보다 크거나 같다면 answer값을 mid로 갱신한 뒤,
      왼쪽 절반을 버리고 오른쪽 절반을 탐색하기 위해 left = mid + 1로 갱신해 준다.
   4. count의 값이 n보다 작다면 왼쪽 절반을 탐색하기 위해 right = mid - 1로 갱신해 준다.
5. left와 right가 만나면, 즉 탐색이 끝나면 answer 길이를 출력한다.

 

Java

 

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

public class Prob1654 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int k = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

		long[] lengths = new long[k];
		long max = 0;

		for (int i = 0; i < k; i++) {
			lengths[i] = Long.parseLong(br.readLine());
			max = Math.max(max, lengths[i]);
		}

		long left = 1;
		long right = max;
		long answer = 0;

		while (left <= right) {
			long mid = (left + right) / 2;
			long count = 0;

			for (int i = 0; i < k; i++) {
				count += lengths[i] / mid;
			}

			if (count >= n) {
				answer = Math.max(answer, mid);
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}

		System.out.println(answer);
	}
}

결괏값을 비롯한 숫자들을 반드시 long으로 선언해야 한다.

 

그렇지 않으면 50%에서 틀리게 된다.

 

Python

 

import sys

k, n = map(int, sys.stdin.readline().rstrip().split())
length_lst = [int(sys.stdin.readline().rstrip()) for _ in range(k)]

left = 1
right = max(length_lst)
answer = 0

while left <= right:
    mid = (left + right) // 2
    cnt = 0

    for i in range(k):
        cnt += length_lst[i] // mid

    if cnt >= n:
        answer = max(answer, mid)
        left = mid + 1
    else:
        right = mid - 1

print(answer)

 

Performance