[백준] 20929. 중간

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

문제요약

• interactive 문제
• ${N = 2^k}$ 크기의 배열 두 개가 주어짐(쿼리만 가능)
• 오름차순으로 정렬했을때 N번째 숫자 알아내기
• A/B 배열에서 x번째 숫자가 무엇인가?
• 쿼리는 최대 40회, k <= 19
• 공식해설은 여기에 있다고 함 : https://www.acmicpc.net/board/view/64488

접근법

• 이분탐색이긴 한데 까다로웠음
• 장황하게 구현했는데, 짧게 구현한 코드를 보기 전에 기록해봄
• A의 절반, B의 절반번째 숫자를 얻어낸 후 비교
  • 한쪽이 크면 일단 "작은 쪽 절반들" 보다 큰 구역을 알게됨
    • "작은 쪽 절반들"의 크기가 N보다 크면 => 큰 구역에는 답이 존재하지 않을 것임. 제거
    • "작은 쪽 절반들"의 크기가 N보다 작으면 => 딱히 할 일이 없음
  • 비슷하게 작은 구역에 초점을 맞춰보면
    • "작은 쪽 절반들"의 크기가 N보다 작으면 => 작은구역이 아무리 커도 N은 안될 것임. 제거. 단 앞으로 구할 순서는 "N - 작은구역의 크기" 번째가 될 것임
• 한번의 절반의 비교에서 A쪽의 절반이 사라지던가, B쪽의 절반이 사라지면서 범위를 좁혀나갈 수 있음
• 예외처리
  • 범위를 좁히다가 한쪽의 크기가 1이되면 로직이 적용이 안됨
  • 진행방식은 동일하지만 1일때의 처리를 별도로 수행해줘야함