백준 1654 랜선 자르기 c++, Kotlin (이분 탐색) 2022-06-26 코틀린 추가

문제 출처 : https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 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개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

힌트

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

알고리즘 분류

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

풀이

2021.10.15 - [알고리즘 문제 풀이/프로그래머스] - 프로그래머스 입국심사 c++ (이분 탐색)

위와 동일한 알고리즘인 파라메트릭 서치(Parametric Search)(이분 탐색)으로 풀어야 하는 문제이다.

우선 완전 탐색으로 접근해 보면, 우리는 랜선의 길이를 1부터 주어진 k 개의 랜선 길이 중 가장 긴 802까지 일일이 잘라가면서, 길이(x)로 잘랐을 때 개수가 n 이상이면서 가장 긴 길이를 찾아야 한다.

k가 최대 10000이고, 랜선의 최대 길이는 23^-1인 int의 마지막 범위이기 때문에 선행 알고리즘으로 풀면 시간 초과가 날 수밖에 없다.

길이 별로 몇 개의 랜선이 나오는지 확인하는 접근 방식은 틀리지 않았다.

다만, 거기에 탐색 시간을 O(log랜선길이)로 줄여줄 이분 탐색이란 스킬이 필요한 것이다. 

자르게 될 랜선의 길이를 x라 하자.

이분 탐색 알고리즘을 이용한 풀이는 다음과 같다.

1. x의 범위는 1부터 최댓값인 802에 1을 더해주어 1~802의 범위를 표현하자.

2. 중간 값인 402 == (803+1)/2로 잘랐을 때의 개수를 구한다.

3. 개수를 구하는 방법은 k개의 랜선을 402로 나눈 몫을 더하는 것이다.

4. 개수가 n 이상이면 답이 될 수 있으므로 result를 갱신한다.

5. 402로 자른 랜선들의 개수가 n 개 미만이므로, 랜선의 길이를 다시 반절로 줄여본다.

6. 201 ==(1+402)/2로 자른 랜선들의 개수가 n 개 미만이므로, 랜선의 길이를 다시 반절로 줄여본다.

7. 101 ==(1+201)/2으로 자른 랜선들의 개수가 n 개 이상이므로, result를 갱신하고, 101을 시작점, 201을 끝 점으로 두고 다시 151 == (101+201)/2로 잘라본다.

8. 위의 과정을 자른 랜선들의 개수가 n 개 미만이 될 때까지 반복한다.

 

피곤해서 그런지 풀이가 깔끔하지 않다.

쉽게 말하면

start

...

mid

...

end

start가 최소 길이

mid가 검사할 중간 길이

end가 최대 길이

라고 할 때,

start~ end 길이에 따라 mid를 검사하여, mid 길이로 자른 개수가 n보다 작다면 더 짧은 길이의 길이로 잘라야 하므로

현재 mid기준 왼쪽 구간(start~mid)를 검사해 나가면 되고, mid 길이로 자른 개수가 n보다 크거나 같다면 답이 있는 구간은 현재 mid기준 오른쪽 구간(mid+1~end)를 검사해 나가며 답을 갱신하면 된다.

mid = (start+end)/2의 과정에서 mid가 int의 범위를 초과할 수 있다는 점에 주의하자.

 

이해가 가지 않거나, 오류가 있다면 댓글로 알려주세요!

 

2022-06-26

이 문제는 이분 탐색의 한 종류인 '파라메트릭 서치'이다.

파라메트릭 서치란 개념을 모르고 이분 탐색만 구현할 줄 알면 충분히 응용해서 풀 수 있다.

개인적인 생각으로 이분 탐색과 가장 큰 차이는 mid값이 답이 될 수 있는지 확인하는 로직이 따로 필요하단 점이다.

 

코드1 (c++)

#include<iostream>
#include<algorithm>
using namespace std;

//n개 이상 만들기
//기존 길이가 제각각인 k개의 랜선을 잘라서 n개의 같은 길이 랜선으로 만들기
//최대 랜선 길이
//1<=k<=10000
//1<=n<=1000000
//k<=n
//k랜선의 길이는 항상 2^31-1이하 자연수
//길이 최소 1 길이 최대 
int k, n;
long long input[10000];
long long result = 0;

int cnt(int len) {
	int count = 0;
	for (int i = 0; i < k; i++) {
		count += input[i] / len;
	}
	return count;
}

void biSearch(long long start,long long end) {
	if (start >= end) {
		return;
	}
	long long mid = (start + end) / 2;
	int count = cnt(mid);
	if (count < n) {
		biSearch(start, mid);
	}
	else {
		result = max(result, mid);
		biSearch(mid + 1, end);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> k >> n;
	long long maxLen = 0;
	for (int i = 0; i < k; i++) {
		cin >> input[i];
		maxLen = max(maxLen, input[i]);
	}
	biSearch(1, maxLen+1);
	cout << result;
	return 0;
}

코드2 (Kotlin)

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
lateinit var kArr: IntArray

fun check(search: Long): Long = kArr.sumOf { it/search }

fun main() = with(System.out.bufferedWriter()){
    //input
    val (k,n) = getIntList()
    var maxLen = 0
    kArr = IntArray(k){ getInt().apply { maxLen = maxLen.coerceAtLeast(this) }}
    //solve
    var s: Long = 1L
    var e: Long = maxLen.toLong()
    var answer =0L
    while(s<=e){
        val mid: Long = (s+e)/2
        //가능하면 더 늘려보기
        if(check(mid)>=n){
            s= mid+1
            answer = answer.coerceAtLeast(mid)
        }
        else{
            e = mid-1
        }
    }

    write("$answer")
    close()
}