오늘 뭐했지

https://boj.ma/1756/t 

깊이 별 오븐의 지름과 오븐에 넣으려고 하는 피자 반죽의 지름들이 주어집니다.

반죽을 모두 오븐에 넣으려고 할때 가장 높이 위치하는 반죽의 높이를 출력하는 문제입니다.

완전탐색부터 접근해봅니다.

반죽은 만든 순서대로 넣기때문에 반죽의 지름이 저장된 배열을 앞에서부터 모두 확인하며

오븐의 지름이 저장된 배열에서 처음으로 반죽의 지름보다 작아지는 위치의 바로 앞에 반죽을 넣으면 됩니다.

하지만 오븐의 지름이 주어지는 배열의 크기가 최대 30만, 반죽의 개수도 최대 30만이기 때문에

최악의 경우

입력이

300000 300000

300000 299999 299998 ... 1

1 2 3 ... 300000

형태로 주어진다면

O(300000 * 300000)이기 때문에 시간초과가 발생합니다.

모든 오븐의 배열을 확인하며 처음으로 나보다 작아지는 위치가 궁금하고 이것을 완전탐색으로 확인하는 것이 오래걸리니

이것을 최적화할 방법을 생각해봅시다.

오븐 배열의 앞에서부터 순회하며 처음으로 나보다 작아지는 위치가 궁금한것이니 나보다 크거나 같은것들에 대해는 신경쓰지 않아도 됩니다.

따라서 어떤 인덱스 i에 대해 0 ~ i위치까지의 최소값만 알면 됩니다. 그럼 반죽이 i위치까지 들어갈 수 있는지 알 수 있습니다.

이것을 저장한 배열을 prefix_min 이라고 하겠습니다.

prefix_min[i] := 오븐배열의 0 ~ i번 값까지의 최소값

이 배열에서 반죽이 들어갈 수 있는 위치중에 가장 깊은 위치에 넣으면 됩니다.

prefix_min 배열의 형태가

5 5 5 4 4 2 2 2 1 1 1

이라고 생각해봅시다.

반죽 지름이 3짜리인 반죽이 위 배열에서 값이 2가 되는 위치 이후로는 절대 답이 될 수 없습니다.

여기서 이분탐색을 떠올려 구현했습니다.

최종적으로 누적합 + 이분탐색을 통해 해결했습니다.

import sys
input = sys.stdin.readline

d, n = map(int, input().split())
oven = list(map(int, input().split()))
pizza = list(map(int, input().split()))
prefix_min = [0] * d
prefix_min[0] = oven[0]
for i in range(1, d):
    prefix_min[i] = min(prefix_min[i - 1], oven[i])
ans = -1
s, e = 0, d - 1
for i in pizza:
    # 반죽이 들어갈 수 있는 위치중 가장 깊은곳 찾기
    s = 0
    tmp = -1
    while s <= e:
        mid = s + e >> 1
        if prefix_min[mid] >= i:
            tmp = mid
            s = mid + 1
        else:
            e = mid - 1
    if ~tmp: # tmp가 -1이 아니라면 == 들어갈 위치를 찾았다
        ans = tmp
        e = tmp - 1
    else: # 못들어감
        print(0)
        exit()
print(ans + 1)

prefix_min 배열만 만들어 놓고 이 배열의 뒤에서부터 순회하며 답을 찾아나가는 방식도 가능합니다.