피자 굽기

아이디어

1. 피자의 사이즈보다 지름이 작은 관이 언제 나오는지 O(D)로 찾으려 하니
   시간복잡도가 O(ND)가 되어버려 시간 초과

2. 어느 지점에 들어갈 수 있는 피자반죽의 최대 크기 MaxRadius 배열을 생각
   이는 내림차순이므로 이진 탐색을 통해 피자 반죽이 들어갈 수 있는 위치를 찾을 수 있음

3. 매개변수 이진 탐색을 통해 찾고자 하는 오븐의 위치를 i라 하자.
   i번째 maxRadius는 반죽의 반지름 크기 이상이어야 하고
   i + 1번째는 반죽의 반지름 크기보다 작아야 한다.

4. 이 때 매개변수 이진 탐색으로 찾을 수 없는 경우가 두가지

(1) 오븐에 들어갈 수 없는 경우
(2) 오븐의 맨마지막에 들어가는 경우

사실 둘 중 하나를 이진탐색으로 처리하지 않고 다른 방법으로 처리하면 나머지는 이진 탐색으로 처리할 수 있지만 둘다 이진 탐색으로 처리하면 오래 걸리므로 if로 따로 처리

코드

import sys
input = sys.stdin.readline

# max radius 리스트를 통해 피자가 어디 들어가야 하는지 리턴하는 함수
def putPizza(size, left, right, maxRadius):
	if left > right:
		return -1
	mid = (left + right)//2
	if size <= maxRadius[mid]:
		if size <= maxRadius[mid + 1]:
			return putPizza(size, mid + 1, right, maxRadius)
		else:
			return mid
	else:
		return putPizza(size, left, mid - 1, maxRadius)

D, N = map(int, input().split())
depth = list(map(int, input().split()))
radius = list(map(int, input().split()))

# max radius 리스트 만들기
maxRadius = []
minimum = 1000000000
for i in range(D):
	if minimum > depth[i]:
		minimum = depth[i]
	maxRadius.append(minimum)

maxDepth = D

for i in range(N):
	if maxDepth == -1:
		break

	if maxRadius[maxDepth - 1] >= radius[i]:
		maxDepth -= 1

	elif maxRadius[0] < radius[i]:
		maxDepth = -1

	else:
		maxDepth = putPizza(radius[i], 0, maxDepth - 1, maxRadius)  # 피자가 마지막으로 들어간 위치

print(maxDepth + 1)

내 코드에서 스스로 궁금한 점

첫째로 이렇게 문제를 풀었는데

만약
4 5
4 4 4 4
5 5 5 5 5

이런 식으로 입력하면 35라인에서 out of range에러가 떠야 할거 같은데 왜 맞는지 모르겠다.

A. maxRadius[-1]은 마지막에서 첫번째 칸을 의미하므로 out of range가 아니다.
그리고 maxRadius[-1]은 maxRadius[0]보다 무조건 작거나 같으므로 저기서 if문에 걸려도 같은 결과가 된다.

단, 더 확실히 하려면 maxRadius == 0인 경우를 따로 처리하는게 맞다.

두번째로

분명 저 안에서 값을 찾을 수 없는 경우는 모두 35, 38라인으로 처리한거 같은데

putPizza 함수의
if left > right: return - 1
부분을 없애면 왜 recursion error가 나는지 궁금하다.

A.
0 부분을 제대로 처리 안 해줘서 그렇다. 제대로 처리하면 다음과 같다.

import sys
input = sys.stdin.readline

def putPizza(size, left, right, maxRadius):
	mid = (left + right)//2
	if size <= maxRadius[mid]:
		if size <= maxRadius[mid + 1]:
			return putPizza(size, mid + 1, right, maxRadius)
		else:
			return mid
	else:
		return putPizza(size, left, mid - 1, maxRadius)

D, N = map(int, input().split())
depth = list(map(int, input().split()))
radius = list(map(int, input().split()))

maxRadius = []
minimum = 1000000000
for i in range(D):
	if minimum > depth[i]:
		minimum = depth[i]
	maxRadius.append(minimum)

maxDepth = D

for i in range(N):
	if maxDepth == 0:
		maxDepth = -1
		break

	if maxRadius[maxDepth - 1] >= radius[i]:
		maxDepth -= 1

	elif maxRadius[0] < radius[i]:
		maxDepth = -1
		break

	else:
		maxDepth = putPizza(radius[i], 0, maxDepth - 1, maxRadius)

print(maxDepth + 1)

다른 사람의 코드

rksxhdals 의 코드

https://www.acmicpc.net/source/36151840

import os, io
#빠른 입출력을 위한 input함수 재정의
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

D, N = map(int, input().split())
arr = list(map(int, input().split()))  # 오븐
pizzas = list(map(int, input().split()))  # 피자들
stack = [[arr[0], 0]]
i = 0

for i in range(len(arr)):
	if arr[i] < stack[-1][0]:
		stack[-1][1] = i - stack[-1][1]
		stack.append([arr[i], i])
stack[-1][1] = D - stack[-1][1]
top = len(stack) - 1

for p in pizzas:
	while top >= 0 and stack[top][0] < p: top -= 1
	if top == -1: print(0); exit()
	stack[top][1] -= 1
	if stack[top][1] == 0: top -= 1
print(sum(stack[i][1] for i in range(top + 1)) + 1)