BOJ 20929 중간

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/20929

🧐 관찰 및 접근
#

문제의 제한인 $2^{19}$와 횟수를 볼때, 이분 탐색을 장려하고 있는 것 같다.
다음과 같은 상황을 생각해보자.
- - 길이 8의 배열 2개에서 다음과 같이 $N/2$번째 수인 4번째 수를 비교했을 때, 위와 같이 작은 배열의 아래 절반과 큰 배열의 윗쪽 절반은 고려할 필요가 없어진다.
- - 위와 마찬가지로, 위에서 작은 배열 쪽 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))

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#