[백준 25907번] 파이썬 - 양과 늑대

백준 25907 - 양과 늑대

시간 제한 1초, 메모리 제한 1024MB

# 조건

• 총 N일 동안 빈 회의장에 늑대와 양이 모이기로 했다. 첫 번째 날부터 N 번째 날까지 매일 양 또는 늑대 한 마리가 회의장에 도착한다.
• 첫 번째 날에는 항상 양이 도착하고 마지막 날에는 항상 늑대의 수가 양의 수보다 많다.
• 늑대와 양의 수가 같아지면 늑대가 양을 잡아먹을 수도 있어 늑대와 양의 수가 같아지는 모든 날에 회의장에 무지가 출근하게 된다.
• 무지의 친구인 당신은 무지가 출근하는 날을 알고 싶다.
• 무지가 언제 출근하는 지 알기 위해 시스템에 특정한 날에 회의장에 있는 양의 수를 물어보고자 한다.
• 최대 20번의 질의를 통해 무지가 출근하는 날을 아무 날이나 하나 출력한다. 만약 그러한 날이 없는 경우 ! 0을 출력한다.
• **시스템은 여러분의 질문에 따라 특정 날에 도착한 동물의 정보를 바꾸지 않는다.
  • 즉, 이전까지의 답변들과 모순되는 답변은 하지 않는다.

입력

• 입력의 첫 줄에 정수 N이 주어진다. (3<=N<=100,000)

출력

• 다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, i번째 날에 회의장에 있는 양의 수를 질의할 수 있다.
• 질의에 대한 답변은 정수로 주어진다.
• ? i : i번째 날 회의장에 있는 양의 수$\left(1 \le i \le N\right)$ 
• 각 질문을 출력한 후에는 반드시 표준 출력 버퍼를 flush 해야 하고, 표준 입력 스트림(stdin)을 통해 질문에 대한 답을 입력받아야 한다.
• 그렇지 않으면, 시간 초과 또는 런타임에러를 받는다.
• 질문하는 i의 범위가 날짜 구간을 벗어나는 경우, 틀렸습니다를 받는다.
• 질문은 최대 20번만 할 수 있고, 이보다 더 많이 질문을 하면 틀렸습니다를 받는다.
• 최대 20번의 질문을 이용해, 정답을 아래의 표준 출력 스트림(stdout)을 이용해 한 번만 출력한다.
• ! T $\left( 0 \le T \le N\right)$ 
• 그 후 반드시 표준 출력 버퍼를 flush해야 하고, 프로그램을 종료한다.
  • 이것은 질문 횟수에 포함되지 않는다.
• 언어 별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.
  • C: fflush(stdout)
  • C++: std::cout << std::flush
  • Java: System.out.flush()
  • Python: sys.stdout.flush()

**# 인터렉티브

• 백준에서 인터렉티브 문제를 보는건 처음이다.
• 인터렉티브 문제란 서버와 나의 코드가 서로 질의응답과 같은 상호작용을 하는 문제이다.

• 인터렉티브 문제는 입출력이 상당히 느리기 때문에 시스템 입출력을 사용해주어야 하고 버퍼에 대해 알아야 한다.
• 버퍼는 임시 메모리 공간을 가지고 있는데 이 중 입출력 버퍼는 입력된 데이터나 출력 장치로 보내기 전에 데이터를 일시 저장한다.
• 채점 프로그램에서 이런 방식은 제대로 돌아가지 않을 수 있기 때문에 **플러쉬(FLUSH)를 사용하여 지속적으로 버퍼를 비워주어야 한다.
• 인터렉티브 문제의 특징은 스스로 질문자가 되어야 하기에 디버깅이 불가능하다.

# 접근 방법

• 문제를 읽다보니 스무고개와 비슷하다는 생각이 들었다.
  • 첫 날에는 항상 양이 도착하고, 마지막 날에는 항상 늑대의 수가 양의 수보다 많다.
  • 매일 양 또는 늑대 한 마리가 도착한다.
  • 또한, 늑대와 양의 수가 같으면 늑대가 양을 잡아먹을 수도 있기에 늑대와 양의 수가 같아지는 모든 날에는 무지가 출근한다.
• 이분탐색을 이용하여 풀어주면 될 것 같다.
• start = 1, end = 주어진 N으로 시작하여 질문이 20개까지만 하도록 while문을 돌려준다.
• mid를 (start+end) // 2로 print(? mid)를 해주면 그 날의 양의 수가 입력으로 들어온다.
• 이 때, mid(날짜) - val(그날의 양의 수) == val 이라면 늑대와 양의 수가 동일하다는 뜻이다.
  • 매일 한 마리의 양 또는 한 마리의 늑대가 오므로
  • 같은 경우 무지가 출근 했으므로 print(! mid) 후 exit()
• 만약 mid - val > val 이라면 늑대의 수가 많으므로 end = mid - 1
• mid + val < val 이라면 양의 수가 많으므로 start = mid + 1

import sys  
input = sys.stdin.readline  
N = int(input())  
start = 1  
end = N  
cnt = 0  

while cnt < 20:  
    mid = (start + end) // 2  
    print(f'? {mid}')  
    sys.stdout.flush()  
    val = int(input())  

    if mid - val == val:  
        print(f'! {mid}')  
        sys.stdout.flush()  
        exit()  

    elif mid - val > val:  
        end = mid - 1  

    elif mid -val < val:  
        start = mid + 1  

    cnt += 1