문제 링크

피자 굽기

문제 설명

N개의 피자 반죽이 있을때, 피자 반죽을 완성되는 대로 오븐에 넣으려고 한다. 근데 오븐이 일자가 아니라 와 같이 이상하게 생겼다,, 오븐의 깊이는 맨 위부터 1,2,3,,,,D이다. 이렇게 N개의 피자가 오븐에 모두 들어가고 나면, 맨 위의 피자가 얼마나 깊이 들어가는지 구하시오.

문제 풀이

시도 1

이분탐색의 대상을 오븐의 지름이 담긴 리스트로 두었다. 입력으로 받은 오븐 리스트를 오름차순으로 정렬한다.

오븐에 피자를 넣을 수 있는 조건이
1. 내 피자의 지름보다 지름이 작은 위치 바로 위에
2. 제일 위에 놓인 피자보다 위에
이므로
각각의 피자에 대해서 이분탐색을 이용해 oven_list중에서 피자 지름보다 작은 것 중에 제일 낮은 오븐찾아서 그 위에 올리고, last_idx로 제일 나중에 얹은 피자의 오븐 idx를 저장했다,,

import sys
input = sys.stdin.readline

#오븐의 깊이, 피자 반죽 개수
D, N = map(int, input().split())
oven = list(map(int, input().split()))
oven_list = list(enumerate(oven))
pizzas = list(map(int, input().split()))

#오븐의 지름 오름차순으로 소팅
oven_list = sorted(oven_list, key= lambda x: x[1])

def binary_search(pizza_radius, last_idx):
    #oven_list중에서 피자 지름보다 작은 것 중에 제일 낮은 오븐찾기
    start, end = 0, len(oven_list)-1
    while start <= end:
        mid = (start+end)//2
        if oven_list[mid][1] < pizza_radius:
            start = mid + 1
        else:
            end = mid - 1
    if end == -1 or end == len(oven_list)-1:
        return end
    max_val = oven_list[end][0]
    for i in range(end):
        if max_val < oven_list[i][0] < last_idx:
            max_val = oven_list[i][0]
    return max_val

last_idx = D
for pizza in pizzas:
    idx = binary_search(pizza, last_idx)
    if idx == -1:
        #바로 위에 쌓기
        last_idx -= 1
    elif idx == len(oven_list)-1:
        print(0)
        sys.exit(0)
    else:
        last_idx = idx-1

print(last_idx+1)

시도 2

https://rhdtka21.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-BOJ-1756-%ED%94%BC%EC%9E%90-%EA%B5%BD%EA%B8%B0님 풀이를 참고해서 풀었읍니다,,

import sys
input = sys.stdin.readline

#오븐의 깊이, 피자 반죽 개수
D, N = map(int, input().split())
oven = list(map(int, input().split()))
pizza = list(map(int, input().split()))

#지금까지 나온 오븐의 지름 중 가장 작은 값으로 바꿔줌
for i in range(1, D):
    oven[i] = min(oven[i], oven[i-1])
    
count = 0
last_idx = D-1

#오븐의 맨 밑부터 탐색
for i in range(D-1, -1, -1):
    #모든 피자 넣으면
    if count >= len(pizza):
        print(last_idx+1)
        sys.exit(0)
    #피자의 지름보다 오븐의 지름이 크면 -> 넣을 수 있음
    if oven[i] >= pizza[count]:
        count += 1
        last_idx = i
print(0)

1. 입력받은 오븐의 지름을 쭉 순회하면서 지금까지 나온 오븐의 지름 중 가장 작은 값으로 바꿔줌
   : 주어진 테케의 경우 [5, 6, 4, 3, 6, 2, 3] ->
   [5, 5, 4, 3, 3, 2, 2]
2. 오븐의 맨 밑부터 탐색하면서, 오븐의 지름이 피자의 지름보다 크거나 같으면 넣어주고, 모든 피자를 넣으면 가장 상단 인덱스를 리턴해준다.

아놔 넘 어렵네 ,, 다시 풀어봐야겠다,, 그냥 오븐 잘 만들면 안되나요 ㄱ-
아침에 일어나서 보니까 처음에 문제 이해를 잘못한거같다. 맨 밑에서부터 넣어야 한다길래 맨 위에서부터 쌓는다고 생각함ㅋㄷ,,,