[백준] 1654번 랜선 자르기

 

 

 

 

문제

 

소스코드

ㅎ#include<iostream>
#include<vector>
using uint_t = unsigned long long;
void Parametric_Search(uint_t, uint_t);
uint_t maxLen;
uint_t k, n, max = 0;
std::vector<uint_t> lanList;


int main() {
	std::cin >> k >> n;

	for (uint_t i = 0; i < k; ++i) {
		uint_t input;
		std::cin >> input;

		if (max < input)
			max = input;

		lanList.emplace_back(input);
	}

	Parametric_Search(1,0xFFFFFFFFUL);
	std::cout << maxLen;
}

void Parametric_Search(uint_t min, uint_t max) {

	while (min <= max) {

		uint_t mid = (min + max) / 2;
		uint_t temp = 0;
		
		//나눈다.
		for (auto i : lanList)
			temp += (i / mid);


		//Left N이 더 크다면 최소조건을 만족하지 못했으니 더 길이를 더 줄인다.
		if (temp < n) {
			max = mid - 1;

		}
		//right 일단 최소조건을 만족하지만 확실치 않으니 오른쪽으로 간다.
		else {
			min = mid + 1;
			maxLen = mid;
		}
		
	}
	
}

 

 

후기

이진 탐색의 응용 버전 파라매트릭 서치(Parametric Search)를 사용하여 구현을 하였다. 이진 검색 문제는 문제를 보고 어떤 기준으로 어떻게 나눌까를 얼마나 빨리 이해하냐가 핵심인 거 같다.

 

알고리즘의 상세내용은 다른 블로그에 자세히 설명하신 분들이 많기 때문에 생략하겠다.

 

 

 

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/1654