[이분탐색 - Parametric Search] 삼 오 무

문제링크

https://www.codetree.ai/missions/8/problems/three-five-moo?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 특정 숫자가 몇 번째 위치하는지 파악하기 → find_seq 함수
  • 8은 5번째 숫자이다. 이유는 8 앞에 3의 배수는 3, 6  / 5의 배수 5가 존재한다. 따라서 원래 8번째 수인 8 앞에 '무'로 만들어야할 숫자가 3개이다. 따라서 8 - 3 = 5번째 숫자가 된다.
  • 16은 9번째 숫자이다. 이유는 16의 앞에 3의 배수는 3,6,9,12,15 / 5의 배수는 5,10,15가 존재한다. 15의 배수인 15가 중복으로 빼진다. 따라서 16 앞에 '무'로 만들어야 할 숫자는 3의배수(5개) + 5의배수(3개) - 15의배수(1)로 16 - 5 - 3 + 1 = 9번째 숫자가 된다.
• 8은 5번째 숫자라는 정답을 가지고 어디 l, r, ans를 갱신할 곳의 위치를 찾아보자.
  • 8, 9, 10 모두 find_seq에 의하면 5번째 숫자이다.
  • 1 ~ 7 (F) || 8 ~ 10 (T) 인 상황이다. 따라서 T인 상황 중 가장 작은 값을 찾아야 한다. r을 최대한 감소시키면서 n보다는 크거나 같게 만들어야 한다.

2. 코드(Python)

# n이 최대 10^9번째...n은 10^9버째를 찾기 위해서는 그것보다 훨 클 것!
n = int(input())
# 7이 4번째인 이유: 7번째인 7앞에 3의배수 2개, 5의 배수 1개가 있어서 7 - 3 = 4번쩨
# 숫자 n이 몇 번째인가? -3의배수 -5의배수 +15의배수

def find_seq(num: int):
    return num - num // 3 - num // 5 + num // 15

# n이 되는 mid 중 최솟값을 찾기.
# find_seq(8) = 5
# 1 2 2 3 3 3 4(F) | (T)5 5 5 
def binary_search(target_n: int):
    l, r = 1, int(1e15)
    ans = 1
    while l <= r:
        mid = (l + r) // 2
        if find_seq(mid) >= n:
            ans = mid
            r = mid - 1
        else:
            l = mid + 1
    return ans
    
print(binary_search(n))