[BOJ] 피자 굽기 - 1756 (G5)

시간 제한	메모리 제한
2 초	128 MB

문제

오븐은 원통 모양이며 깊이 D이다. 각 깊이마다 지름이 다르다. 반죽을 넣을 때 위에서부터 차례대로 넣는다. 반죽이 오븐보다 크면 해당 위치에 걸린다.

모든 반죽을 넣었을 때, 마지막 반죽이 들어간 깊이를 구하는 프로그램을 작성하시오.

풀이

구현 문제이다. 각 위치에서 그 위의 최소값을 미리 계산해둔다.

코드

import sys
input = sys.stdin.readline

D, N = map(int, input().split())
oven = list(map(int, input().split()))
doughs = list(map(int, input().split()))

min_oven = oven[0]
for i in range(1, D):
    min_oven = min(min_oven, oven[i])
    oven[i] = min(oven[i], min_oven)

oven_i = D - 1
dough_i = 0

while dough_i < N:
    if oven[oven_i] < doughs[dough_i]:
        # 못들어감
        oven_i -= 1
        if oven_i < 0:
            # 다 들어갈 수 없음
            print(0)
            break
    else:
        dough_i += 1
        oven_i -= 1

else:
    print(oven_i + 2)

시간 복잡도

O(D + N)