백준 1654번
랜선 자르기, 이분 탐색
PYTHON
Parametric Search
이 문제는 이분 탐색의 원리를 이용한 parametric search를 이용하여 해결한다.
parametric search의 간단한 설명을 제시한다.
Parametric Search
Parametric search 이분 탐색의 원리를 이용한 탐색 방식으로
특정 변수의 최대 또는 최소를 구하는 최적화 문제를 결정 문제로 바꾸어 해결하는 방식이다.
이분 탐색처럼 범위를 절반씩 줄여나가는 것으로 알고리즘의 효율성을 챙긴다.
따라서 어떤 변수를 탐색의 대상으로 삼는 지 결정하는 것이 중요하다.
문제 해결
랜선 자르기 문제에서는 자르려는 길이가 탐색의 대상이 된다.
현재 문제 조건에서 최대 길이로 삼을 수 있는 길이는 802이므로 오른쪽 끝 경계는 802로 왼쪽 끝 경계는 1로 시작한다.
이렇게 시작해서 선택한 랜선의 길이를 통해 N개의 랜선을 만족하는 최대 길이를 구해야 하는데 이 탐색은 이분 탐색의 종료 조건과 동일하다.
왼쪽 경계가 오른쪽 경계를 넘어서는 경우가 탐색 종료의 조건이다.
아래에 소스 코드를 제시한다.
소스 코드
재귀를 이용해 범위를 좁히며 탐색을 진행한다.
tmp 값은 우리가 랜선의 길이를 mid로 선택했을 때, 만들 수 있는 랜선의 개수를 의미한다.
이 값이 우리의 목표인 goal 이상이 되어야 해답의 후보가 될 수 있다.
Whiplash We Flash