[백준]1756 피자굽기 #dp#정석

dp가 어떻게 쓰이는지 직관적으로 와닿는 문제.

​

1. 시간초과 코드

피자를 순서대로 위에서부터 들어갈 수 있을 때 까지 넣어보는 방식.

*시간복잡도 O(피자수*오븐깊이)

from collections import deque

D,N=map(int,input().split())
oven=[9876543210]+list(map(int,input().split()))+[0]
pizza=deque(list(map(int,input().split())))

#바닥임
bottom=D+1
i=100
for i in range(N):
    temp=pizza[i]
    for d in range(1,bottom+1):
        if oven[d]<temp:
            oven[d-1]=0
            bottom=d-1
            break
    if bottom==0:
        break

#끝까지 갔다
if i==N-1:
    print(bottom)
else:
    print(0)

 

2. dp (통과)

oven[i] : 오븐의 i까지들어갈 수 있는 피자의 최대 지름.

위와같이 바꾸면 오븐의 밑에서부터 피자를 순서대로 채워나가며, 한번의 포문으로 답을 찾을 수 있다.

*시간복잡도 O(오븐깊이)

from collections import deque

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

for i in range(1,D):
    if oven[i-1]<oven[i]:
        oven[i]=oven[i-1]

ans=0
pizzaIndx=0
for d in range(D-1,-1,-1):
    if oven[d]>=pizza[pizzaIndx]:
        pizzaIndx+=1
        if pizzaIndx==N:
            ans=d+1
            break

print(ans)