[Python/파이썬] 백준 17393번 다이나믹 롤러

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

코드

n = int(input())
inks = list(map(int, input().split()))
viscosities = list(map(int, input().split()))


def binary_search(start, target):
    l, r = start, n-1
    res = n-1
    while l <= r:
        mid = (l+r)//2
        if viscosities[mid] <= target:
            res = mid
            l = mid+1
        else:
            r = mid-1
    return res


ans = []
for i in range(n):
    ans.append(binary_search(i, inks[i])-i)

print(*ans)

 

칸이 최대 10^18개까지 존재하고, 점도지수가 오름차순으로 정렬된채로 주어지므로 이분탐색을 쓰라는 문제인 것을 알 수 있다.

 

현재 칸에서부터 오른쪽 끝칸 중에서 점도지수가 현재 칸의 잉크 지수(A_i) 이하인 칸을 찾으면 된다. 이때 예제 1의 10, 10, 10과 같이 점도지수가 같은 값이 연달아서 나오는 경우도 있으므로 이분탐색을 할 때 타겟값을 찾았다고 바로 리턴하면 안되고 최대한 탐색하도록 함수를 구현해야 한다.