티스토리 뷰

728x90
반응형

랜선 자르기 문제는 이진 탐색을 활용한 문제입니다. 랜선 길이의 최소값과 최대값을 통해 가장 작게 자를 수 있는 길이, 크게 자를 수 있는 길이를 구할 수 있습니다. 이 범위 내의 길이로 랜선을 잘라서 문제에서 요구하는 개수 이상을 만들고면서 동시에 길이를 최대화하여야 합니다. 이 길이를 찾기 위해서 이진탐색을 활용합니다. 범위의 가운데 길이로 랜선을 잘랐을 때 나오는 개수가 원하는 개수보다 작다면 토막의 길이는 더욱 작아져야하므로 범위의 상한을 가운데보다 1만큼 작은 값으로 변경합니다. 잘랐을 때 나오는 개수가 많거나 같으면 가운데 길이 미만의 길이로 나누었을 때는 더 작은 토막길이로 더 많거나 같은 랜선 토막을 만들어낼 수 있다는 의미가 되므로 범위의 하한을 가운데 길이로 변경합니다. 가운데 길이보다 1만큼 큰 값으로 하한을 변경하지 않은 이유는 가운데 길이가 우리가 원하는 개수보다 많거나 같은 랜선 토막을 만들어낼 수 있는 최대 값일 가능성이 있기 때문입니다. 이진 탐색을 답이 될 수 있는 값의 존재 범위를 차근차근 좁혀나가는 알고리즘이기 때문에 답의 가능성이 있다면 반드시 가지고 있어야 합니다. 

이러한 방식의 알고리즘은 상한과 하한이 같거나 혹은 1만큼의 차이가 나지 않는다면 가운데가 상한과 하한 사이에 있게 됩니다. 따라서 반복해나갈수록 탐색하게 될 범위를 줄어들게 됩니다. 결국은 상한과 하한이 1만큼 차이가 나거나 같아지게 됩니다. 이때 탈출 조건을 명확히 해주지 않으면 무한히 반복하여 프로그램이 종료되지 않을 수 있습니다.

상한과 하한이 1만큼 차이가 나는 경우 상한이 조건을 만족한다면 상한을 출력하고, 그렇지 않으면 하한을 출력합니다. 문제에서는 답이 있는 경우만 테스트 케이스로 주어지므로 하한이 조건(토막의 개수가 많거나 같음)을 만족하지 않는 경우는 없습니다.

상한과 하한이 같다면 상한이나 하한 중 하나를 출력하면 됩니다. 역시나 문제에서 답이 존재하지 않는 경우는 없으므로 해당 값이 답이 되어야 합니다. 그렇지 않는다면 문제의 조건과 모순이 되는 상황이 발생합니다.

느낀점으로 이진 탐색이나 upperbound, underbound 알고리즘을 설계하고 구현할 때는 알고리즘의 루프 불변성을 이용하여 반드시 해당 알고리즘의 타당성을 증명하고 이해해야 할 필요가 있다고 생각하였습니다. 정형화된 코드를 외워서 풀 수 있는 문제도 있지만 그렇지 않을 문제라면 알고리즘을 커스텀하고 그것이 제대로 동작하는 지 확인할 수 있어야 합니다.

작성한 코드는 다음과 같습니다.


#include<stdio.h>

long long N, K;
long long Klen[10020];

long long max = 0;
long long min = 0b01111111111111111111111111111111;
long long mean;
long long high;
long long low;

long long binary(long long a, long long b) {
	long long mid;
	long long sum;
	while (a<b) {
		if (b - a == 1) {
			sum = 0;
			for (long long i = 0; i < K; i++) {
				sum = sum + Klen[i] / b;
			}
			if (sum >= N) {
				return b;
			}
			else {
				return a;
			}
		}

		mid = (a + b) / 2;
		sum = 0;
		for (long long i = 0; i < K; i++) {
			sum = sum + Klen[i] / mid;
		}
		if (sum > N) {
			a = mid;
		}
		else if (sum < N) {
			b = mid - 1;
		}
		else
			a = mid;
	}

	return a;
}

int main(void) {

	scanf("%lld %lld", &K, &N);

	for (int i = 0; i < K; i++) {
		scanf("%lld", &Klen[i]);
		if (max < Klen[i]) max = Klen[i];
		if (min > Klen[i]) min = Klen[i];
	}
	mean = (N / K);
 
	high = max / mean;
	low = min / (mean + 1);

	printf("%lld\n", binary(low, high));
}

문제의 지문은 다음 링크에서 확인할 수 있습니다.

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

728x90
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
반응형
250x250