Binary_search

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34609 번역 문제 # $1$번부터 $n$번까지 번호가 매겨진 $n$송이의 꽃이 왼쪽에서 오른쪽으로 일렬로 놓여 있다. 각 꽃은 백합(lily) 또는 장미(rose) 중 하나이다. $0$ 이상 $n$ 이하의 정수 $j$에 대해, $l_j$를 왼쪽 $j$개의 꽃 중 백합의 수, $r_j$를 오른쪽 $n - j$개의 꽃 중 장미의 수라 하자.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31498 🧐 관찰 및 접근 # 집 - 토카 - 돌돌이 형태로 있는 것 같다. 매 수행마다 토카는 $B, B-K, B-2*K \cdots$ 만큼 움직이고, 돌돌이는 $D$만큼 계속 움직인다. 토카가 잡힌다면, 그 순간 토카가 움직인 길이는 $D$보다 작을 것이다. 따라서 토카가 어느 순간 잡혔다면, 토카와 돌돌이가 계속 움직인다고 가정하면 돌돌이는 토카보다 훨씬 왼쪽에 있게 된다. 따라서 시간에 토카와 돌돌이의 위치에 단조성이 존재한다. 이분 탐색을 이용할 수 있겠다. 토카가 집에 도착하지도 못하는 상황, $K$가 0인상황 등 여러가지 예외 상황을 조심하자. 💻 풀이 # 코드 (python): A, B = map(int, input().split()) C, D = map(int, input().split()) K = int(input()) # 토카가 집에 도착할 수는 있는가? # B + (B-K) + (B-2K) + ... >= A if K > 0: # K = 0이면 무조건 도착할 수 있음 cnt = B // K # B - cnt * K >= 0 인 최대 cnt tot = B * (cnt + 1) - K * (cnt * (cnt + 1)) // 2 # B + (B-K) + ... + (B - cnt * K) if tot < A: print(-1) exit(0) # 토카가 집에 도착하는 타이밍이 돌돌이보다 이른가? def toka_move(time): if K > 0: time = min(time, B // K + 1) return B * time - K * (time * (time - 1)) // 2 ok, ng = 10**12, 0 # 토카가 집에 도착하는 가장 빠른 타이밍 while ok - ng > 1: mid = (ok + ng) // 2 if toka_move(mid) >= A: ok = mid else: ng = mid if D*ok < A + C: # 아직 돌돌이가 도착하지 않았다면 print(ok) else: print(-1) 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/20929 🧐 관찰 및 접근 # 문제의 제한인 $2^{19}$와 횟수를 볼때, 이분 탐색을 장려하고 있는 것 같다. 다음과 같은 상황을 생각해보자. ![[Drawing 2026-02-10 14.25.24.excalidraw.png]] 길이 8의 배열 2개에서 다음과 같이 $N/2$번째 수인 4번째 수를 비교했을 때, 위와 같이 작은 배열의 아래 절반과 큰 배열의 윗쪽 절반은 고려할 필요가 없어진다. ![[Drawing 2026-02-10 14.31.00.excalidraw.png]] 위와 마찬가지로, 위에서 작은 배열 쪽 4개를 제외하고 보면 $N$이 절반으로 줄어든 상황에서 같은 방식으로 반복할 수 있음을 알 수 있다. 따라서 위와 같은 과정을 1개가 남을때까지 반복하면 두 값은 각각 $N, N+1$번째 값일 것이다. 문제에서는 $N$번째 수를 요구했으므로, 더 작은 수를 출력하자. 💻 풀이 # 코드 (python): def Query(s, idx): """ 질문 "? s idx"을 하고 입력받는 함수 """ print("?", s, idx) return int(input()) N = int(input()) A_Lidx = 1 A_Ridx = N # [A_Lidx ~ A_Ridx] 에 정답 후보가 있음 B_Lidx = 1 B_Ridx = N # [B_Lidx ~ B_Ridx] 에 정답 후보가 있음 while A_Ridx > A_Lidx: A_mid = (A_Lidx + A_Ridx) // 2 B_mid = (B_Lidx + B_Ridx) // 2 A_ret = Query("A", A_mid) B_ret = Query("B", B_mid) if A_ret <= B_ret: A_Lidx = A_mid + 1 B_Ridx = B_mid else: A_Ridx = A_mid B_Lidx = B_mid + 1 A_ret = Query("A", A_Lidx) B_ret = Query("B", B_Lidx) print("!", min(A_ret, B_ret)) 🔒 구현 코드 잠금