100년 뒤 개발자 한승규입니다.

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

공유기와 비슷하게 함수를 만들고 하나씩 돌아가면서 확인하도록 만들었다.

import sys

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().split()))

A.sort()

result = 0


def isGood(goal):
    left, right = 0, N - 1

    while left < right:
        if A[left] + A[right] == A[goal]:
            if left == goal:
                left += 1
            elif right == goal:
                right -= 1
            else:
                return True
        elif A[left] + A[right] > A[goal]:
            right -= 1
        elif A[left] + A[right] < A[goal]:
            left += 1


for i in range(N):
    result += 1 if isGood(i) is True else 0

print(result)

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

당연하게 이분 탐색으로 풀었다.

이분탐색을 푸는 루틴이 생긴 것 같다.

우선 함수를 만들고 그 함수를 기준으로 left 쪽으로 갈지, right 쪽으로 갈지 정하는 것이다.

이번 문제의 함수에서 반환하는 값은 공유기의 개수이다.

거리를 기준으로 공유기를 놓아보고, 만약 공유기가 더 필요하다면 거리를 늘리는 것이다.

import sys

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

house = []

for i in range(N):
    house.append(int(sys.stdin.readline()))

house.sort()


def wifi(length):
    result = 1
    cur = house[0]
    for i in range(1, N):
        if house[i] >= cur + length:
            cur = house[i]
            result += 1

    return result


left = 1
right = house[-1] - house[0]

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

    if cnt >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)

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

전에 풀었던 나무 자르기와 비슷하다.

당연히 이분탐색으로 바로 풀었고, 결과를 구해주는 함수는 작성했다.

굳이 설명을 더 적지는 않도록 하겠다.

import sys

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

lan = list()
max_lan = 0

for i in range(K):
    cur_lan = int(sys.stdin.readline().strip())
    lan.append(cur_lan)
    max_lan = max(max_lan, cur_lan)


def cur_lan(length):
    result = 0
    for lan_length in lan:
        result += (lan_length // length)
    return result


left, right = 0, max_lan

while left <= right:
    mid = (left + right) // 2
    mid = max(1, mid)
    lan_count = cur_lan(mid)

    if lan_count >= N:
        left = mid + 1
    else:
        right = mid - 1

print(right)

import sys

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

tree = list(map(int, sys.stdin.readline().split()))


def cut(height):
    result = 0
    for i in tree:
        result += max(0, i - height)
    return result


left, right = 0, max(tree)

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

    if cur_height >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)

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

백준 이분 탐색 중에 가장 많이 푼 문제 중 하나일 거 같다.

그냥 Left, Right를 잡고 범위를 좁혀나간 후 푸는 이분탐색 문제이다.

얻을 수 있는 나무의 길이를 구하기 위해 높이에 따라 얻는 나무를 구해주는 함수는 만들어서 사용했다.