📝 문제 정보#
🧐 관찰 및 접근#
- 문제의 제한인 $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$번째 수를 요구했으므로, 더 작은 수를 출력하자.
- ![[Drawing 2026-02-10 14.25.24.excalidraw.png]]
💻 풀이#
- 코드 (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))