[백준 / C언어] 1654번: 랜선 자르기

 

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

1654번: 랜선 자르기

 

난이도: solved.ac 실버 2

 

 

이분 탐색(Binary Search), 매개변수 탐색(Parametric Search)을 활용하면 O(log n)의 시간 복잡도로 풀 수 있는 문제다

 

N개의 랜선을 입력받을 때 배열에 저장하는 동시에 최대값을 찾아 그 최댓값을 right라고 두고

 

left는 길이가 1인 가상의 랜선으로 두었다

 

그리고 while문 안에서 mid = (left + right) / 2 를 계산하여 원하는 값을 찾을 때까지 mid를 이동하는 방식으로 풀었다

 

여기서 주의해야 할 점이 있다 (이 문제의 처참한 정답률 원인...)

 

입력 받은 랜선의 길이의 범위는 최대 2^31 - 1까지이므로

 

mid = left + right에서의 left + right 와 left = mid + 1에서의 mid + 1을 계산할 때 이 값을 넘어버릴 수 있다

 

따라서 mid와 left를 int가 아닌 long long으로 선언해줘야 한다

 

(나는 코드의 깔끔함을 위해 right까지 long long으로 left, mid와 함께 선언해줬다)

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int main() {
	int N, K, i, cnt, max = 0;
	long long mid;
	scanf("%d %d", &N, &K);
	int* arr = (int*)malloc(sizeof(int) * N);
	for (i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
		if (arr[i] > max)
			max = arr[i];
	}

	long long left, right, ans = 0;
	left = 1;
	right = max;

	while (left <= right) {
		mid = (left + right) / 2;
		cnt = 0;
		for (i = 0; i < N; i++)
			cnt += arr[i] / mid;
		
		if (cnt >= K) {
			if (ans < mid)
				ans = mid;
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	printf("%lld", ans);
	free(arr);
	return 0;
}