백준_1756_피자굽기 (python)

● 접근법

d와n의 최대 길이는 300,000이다. 이중 반복문을 쓸 경우 무조건 시간 초과가 발생한다. 그렇다면 여기서 반복 한 번 만에 이 문제를 해결해야 한다는 것을 알 수 있다. 

 

● 풀이법

1. 피자는 자신보다 지름이 작은 오븐 밑으로는 내려 갈 수 없다. 즉, 오븐은 내림차순 정렬(진짜로 sort(reverse = True) 하라는 뜻이 아니다.) 현재 오븐 칸 보다 바로 밑에 있는 칸의 지름이 더 크다면 현재 오븐 칸의 지름으로 밑에 있는 칸의 지름을 바꿔도 된다는 뜻이다.

2. 그 다음 피자를 집어넣을 때 위에서 집어넣으면 의미없는 반복들을 진행해야 하기 때문에 밑에서부터 넣어주면 반복 한번에 피자를 오븐에 넣을 수 있는 지에 대한 여부를 알 수 있게 된다.

 

● 코드

d,n = map(int,input().split())
data = list(map(int,input().split()))
pizza = list(map(int,input().split()))
oven = [data[0]]
for i in range(1, len(data)):
    if data[i] > oven[i-1]:
        oven.append(oven[i-1])
    else:
        oven.append(data[i])

pidx = 0
i = d - 1
while i >= 0:
    if pizza[pidx] <= oven[i]:
        pidx += 1
        if pidx == n:
            break
    i -= 1

if pidx < n:
    print(0)
else:
    print(i + 1)

 

● 회고록

 두 달 전에도 틀렸던 문제이다. 그 때에도 n과 d의 크기가 매우 컸기 때문에 for 문 한 번만에 가야 한다는 사실까지는 알았었다. 겱국 이번에도 답을 떠올리지 못 했고 oven의 크기를 조절했어야 했다는 것을 떠올리지 못 했다. 그리디 문제를 잘 푼다고 생각했지만 너무 단순하게 생각했던 것 같고 2004, 2005년 문제인데도 불구하고 최근 그리디 문제보다 신박했던 것 같다. 유연하게 대처하는 습관을 기르자!