• 출처 : [백준 1756] 피자 굽기

• 알고리즘 : 이진 탐색

• 풀이

  1. 정렬 (https://n-square.tistory.com/21)

     

  2. 이진 탐색

• 이진 탐색 구현 방법

  • 재귀 함수
  • middle 값에 도우가 들어가고 middle+1에 들어가지 않을 때 return

• 소감

  • O(N^2)은 당연히 안될 것 같아서 시도를 안 했다

  • O(N)에 정렬하는 방법이 생각이 안 나서 검색 ㅠ

  • 이후에 피자마다 범위를 줄여나갈 때 리스트 슬라이싱 → 시간 초과

    • → limit 값을 넣어 해결

  • 자꾸 오답

    • → 피자가 남아있을 때 end_idx가 0이면 종료

  • 오답인데 통과인 것 같다

  • 등록 안 된 테스트 케이스가 있는 것 같다

    7 3
    5 6 4 3 6 2 3
    4 4 4
    답: 1(O) 0(X)

코드

import sys

def init():
    d, n = map(int, sys.stdin.readline().rstrip().split())
    oven_list = list(map(int, sys.stdin.readline().rstrip().split()))
    pizza_list = list(map(int, sys.stdin.readline().rstrip().split()))
    return d, n, oven_list, pizza_list


def get_end(start, end, goal, limit):

    if start > end:
        return -1

    middle = (start + end) // 2
    
    # middle에 들어갈 수 있을 때
    if oven_list[middle] >= goal:

        if middle+1 < limit:

            # middle+1에 들어갈 수 있을 때
            if oven_list[middle+1] >= goal:
                return get_end(middle+1, end, goal, limit)
            # middle+1에 들어갈 수 없을 때
            else:
                return middle

        else:
            return middle
    # middle에 들어갈 수 없을 때
    else:
        return get_end(start, middle-1, goal, limit)


d, n, oven_list, pizza_list = init()
# 가능한 지름으로 변환(정렬)
for i in range(0, d-1):
    if oven_list[i] < oven_list[i+1]:
        oven_list[i+1] = oven_list[i]
end = d
for i in range(n):
    # if end == 0:
    #     break
    end = get_end(0, end, pizza_list[i], end)
    if end == -1:
        break
    if end == 0 and i < n:
        # end = -1
        break
if end == -1 or end == 0:
    print(0)
else:
    print(end+1)