[항해99] 이진탐색 - 2

파라메트릭 서치 기법

이진탐색을 이용해 최적화 문제를 풀 수 있다.

어떤 조건에서 가장 최적의 해를 구할 수 있을 지를 이진탐색을 통해서 해결하는 방식을 파라메트릭 서치 기법이라고 한다.

 

어떤 조건을 가지고 계속 왼쪽 오른쪽 값을 조절하면서 조건에 가장 최적화 된 답을 찾는 것이다. 

끝나는 조건이나 왼쪽오른쪽 값을 바꾸는 조건을 문제에서 잘 확인해서 적용해야해서, 이 조건을 유의해서 풀어야 한다.

백준 2512 예산

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

2512번: 예산

예산의 합을 기준으로 판단하도록 하자.

가능한 예산보다 많은 경우엔 가능한 예산만큼, 예산이 더 많은 경우엔 원하는 예산만큼을 표현하면

min ( 가능한 최대 예산, 원하는 예산 ) 

으로 표현할 수 있을 것이다.

T = int(input())
lst = list(map(int, input().split()))
M = int(input())

left = 0
right = max(lst)

while left <= right:
    budget = 0
    mid = (left + right) // 2
    for i in lst:
        budget += min(i, mid)
    # print("__________________")
    # print("left :", left)
    # print("right :", right)
    # print("M :", M)
    # print("budget :", budget)

    if budget <= M:
        left = mid + 1

    else:
        right = mid - 1

print(right)

백준 2805 나무자르기

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

2805번: 나무 자르기

자르는 길이를 i라고 한다면, 잘린 길이는 나무의 길이 - i 가 될것이고, 잘린 길이는 음수가 될 수 없으니까 

max(0, 나무길이 - i) 가 될 것이다. 

잘린 길이의 합은 우리가 원하는 길이보다 많으면서, i가 최소가 되는 i를 구하는 문제였다.

N, M = map(int, input().split())
lst = list(map(int, input().split()))

left = 0
right = max(lst)

ans = 0
while left < right:
    total = 0
    mid = (left + right) // 2
    for i in lst:
        total += max(0, i - mid)
    if total >= M:
        ans = mid
        left = mid + 1

    else:
        right = mid

print(ans)

백준 1654 랜선 자르기

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

1654번: 랜선 자르기

자르는 랜선의 길이가 최대가 되도록 자르는 문제였다.

랜선을 여러번 자르면 여러 개의 랜선이 되니까, 몫나누기를 이용해서 개수를 세고

잘린 랜선이 많거나 같으면 좀 더 길게 자르고, 적으면 더 짧게 자르는 과정을 거쳐서 답을 구한다.

k, n = map(int, input().split())
lst = []

for i in range(k):
    lst.append(int(input()))

left = 1
right = max(lst)

mid = (left + right) // 2
while left <= right:

    cnt = 0
    for i in lst:
        cnt += i // mid
    # print("-----------------------")
    # print("left :", left)
    # print("right :", right)
    # print("mid :", mid)
    # print("cnt :", cnt)

    if cnt >= n:  # 더 길게 잘라도 돼
        left = mid + 1
        mid = (left + right) // 2

    else:
        right = mid - 1
        mid = (left + right) // 2

print(mid)

 

끝값조건이 꽤나 까다롭다

찾아가는 과정은 할 만한데, 언제 멈출지의 조건은 더 많은 문제를 풀어봐야 알 것 같다.