📗알고리즘

BOJ 1654 랜선자르기
https://www.acmicpc.net/problem/1654

처음 문제를 읽었을 때 이해하기가 굉장히 힘들었다. 이 문제는 Parametric Search 알고리즘을 이용해 해결해야한다.

📚이진탐색(Binary Search)

간단하게만 설명하면 이진탐색(Binary Search)은 정렬된 배열에서 탐색 범위를 절반씩 줄여나가며 O(logN)의 시간복잡도로 탐색하는 값을 찾아내는 알고리즘이다. 크기가 10인 List에서 찾고자 하는 값이 5라면 5라는 해를 찾는 방법이 이진탐색이다.

📚매개변수 탐색(Parametric Search)

Parametric Search는 이진탐색과는 조금 다르다. 이진탐색에서는 값을 주고 이 값을 찾으라는 것이었다면 Parametric Search는 범위나 조건을 주고 이에 만족하는 값을 찾아나가는 방법이다.

무슨말이야

문제를 다시 되돌아보자

802cm, 743cm, 457cm, 539cm 랜선을 주고 11개로 만들었을 때 단 한번에 최대 길이가 200이 된다는 것을 파악하는 것은 불가능하다. 그럼 대충 범위를 지정해놓고(1~802)까지의 범위에서 mid값인 401로 각각의 랜선을 나누어보는것이다(사람은 각 랜선의 길이를 눈대중으로 파악하고 Heuristic하게 값을 파악할 수도 있지만 컴퓨터는 아니므로 중간값에서부터 시작해 데이터를 탐색한다)

802 // 401 => 2개
743 // 401 => 1개
457 // 401 => 1개
539 // 401 => 1개

우리는 11개를 만들어야하는데 5개가 나왔으니 랜선을 더 작은 길이로 나누어야 한다.

그렇다면 401보다 큰 길이의 랜선들은 모두 정답이 아니다. end의 값을 401-1로 조정해서 범위를 수정한다. 그렇다면 start = 1, end = 400, mid = 200이 된다.

802 // 200 => 4개
743 // 200 => 3개
457 // 200 => 2개
539 // 200 => 2개

즉 한번 실행할때마다 가운데 값을 기준으로 범위가 절반이 날아간다 O(logN)

N이 11이 되었으나 아직 200cm가 최대 랜선의 길이라는 것은 아니다. 탐색을 더 진행시켜주어야 한다. 여기서 탐색을 멈추면 최대 길이의 랜선을 구할 수 없다.

200cm보다 짧은 길이는 정답이 아니므로 start의 값을 200+1로 수정해준다. start = 201, end = 400, mid = 300이 된다. 탐색과정에서 start가 end보다 커지면 탐색을 종료한다.

따라서 랜선의 최대 길이를 구하는 최적화 문제에서 랜선의 갯수가 N개 이상인지 아닌지(Yes or No) 확인하는 결정문제로 변화함에 따라 적합한 해의 범위를 절반씩 좁혀나가며 문제를 해결할 수 있다.

📄소스코드

import sys

input = sys.stdin.readline
K, N = map(int, input().split())

lan = [int(input()) for _ in range(K)]


start, end = 1, max(lan)

while start <= end: 
    mid = (start + end) // 2
    cnt = 0 
    for i in range(K):
        cnt += lan[i] // mid
        
    if cnt >= N:
        start = mid + 1
    else:
        end = mid - 1
print(end)

정리: Parametric Search -> 최적화문제를 결정문제로 바꾸는 것
최적화문제를 결정문제로 바꾼다 + Binary Search -> Parametric Search

🔎 참고

https://www.crocus.co.kr/1000
https://sete3683.tistory.com/m/50
https://marades.tistory.com/7
https://heytech.tistory.com/97
https://claude-u.tistory.com/443
https://letsbegin.tistory.com/46
https://jaeryo2357.tistory.com/59
https://jjini-3-coding.tistory.com/11