백준 1637번 파이썬 문제풀이(날카로운 눈) - 이분탐색

---

이 문제의 접근 방식은 https://ji-gwang.tistory.com/431 해당 문제와 굉장히 유사하다. 해당문제의 풀이를 보고 오자.

 

이 문제를 풀기 위해서 3가지의 과정을 떠올려야 한다.

 

1. 누적합(어떤 수 N 보다 작은 수는 몇개 있는지) 즉, (N개까지의 누적합) - (N - 1 개 까지의 누적합)은 N일 때 개수와 같다.

 

2. 이분탐색 ( 찾고하는 수 N을 계속 이분탐색하며 N의 개수가 홀수이면 계속해서 숫자를 낮춰가며 찾아나간다. 단, 짝수이면 숫자를 올려 찾는다. 이렇게 개수가 홀수인 제일 왼쪽지점(즉, 제일 작은값)의 값을 찾아야한다.)

 

3. 딕셔너리에 찾은 값들을 저장해놓고 개수를 구한다. ans가 정답이라면 dp[ans] - dp[ans - 1] 로 구할 수 있다. 단, dp[ans-1]의 값이 존재하지 않을 수 있기 때문에 존재하지 않는다면 다시 함수로 개수를 구해주도록 한다.

 

사실 이문제가 이분탐색이라는 것을 떠올리기가 굉장히 어렵다. 여러모로 좋은 문제였던거 같다. 

(2022-04-01 현재 파이썬3 실행시간 1등 코드이다.)

 

import sys

input = sys.stdin.readline

N = int(input())

nums = []
max_ = 0
dp = {}
for _ in range(N):
    temp = list(map(int, input().split()))
    if max_ < temp[1]:
        max_ = temp[1]
    nums.append(temp)

s = 1
e = max_
ans = 0


def check(mid):

    total = 0

    for i in nums:
        temp_mid = mid

        A, C, B = i[0], i[1], i[2]

        if A > temp_mid:
            continue

        if temp_mid > C:
            temp_mid = C

        total += ((temp_mid - A) // B + 1)

    dp[mid] = total

    return (total % 2) == 1


while s <= e:

    mid = (s + e) // 2

    if check(mid):
        ans = mid
        e = mid - 1
    else:
        s = mid + 1


def count_check(mid):
    total = 0

    for i in nums:
        temp_mid = mid

        A, C, B = i[0], i[1], i[2]

        if A > temp_mid:
            continue

        if temp_mid > C:
            temp_mid = C

        total += ((temp_mid - A) // B + 1)

    return total


if ans:
    if dp.get(ans - 1, 0):
        print(ans, dp[ans] - dp[ans - 1])
    else:
        print(ans, dp[ans] - count_check(ans - 1))
else:
    print("NOTHING")