[BOJ_C++] 1654번 : 랜선 자르기

문제

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int main() {
	int k, n, cnt;
	long long low = 1, high = -999, mid;

	scanf("%d %d", &k, &n);
	int* line = new int[k];
	for (int i = 0; i < k; i++) {
		scanf("%d", &line[i]);
		if (high < line[i]) high = line[i];
	}

	while (low <= high) {
		cnt = 0;
		mid = (low + high) / 2;

		for (int i = 0; i < k; i++)
			cnt += line[i] / mid;

		if (cnt >= n) low = mid + 1;
		else high = mid - 1;
	}

	printf("%d", high);

	return 0;
}

• 이분 탐색을 이용하여 최대 길이를 찾을 예정이다.
• low와 high의 값을 초기화 하기 위해 최소 길이인 1을 low로 초기화 하고, 최대 길이는 랜선의 각 길이를 입력받으며 찾아낸다.
• low가 high보다 작거나 같을 때 까지 mid = (low + high) / 2가 되어 각 랜선을 잘라 얻을 수 있는 개수를 cnt에 저장한다.
• 얻을 수 있는 랜선의 개수가 원하는 랜선의 개수보다 많을 경우 더 긴 랜선을 만들기 위해 low = mid + 1으로 바꿔주고 아니라면 high = mid - 1로 바꿔준다.
• 최종적으로 가장 긴 랜선을 만들 수 있는 길이를 출력하고 프로그램을 종료한다.

 

결과