[Python] BOJ 1756 - 피자 굽기

https://www.acmicpc.net/problem/1756

1756번: 피자 굽기

# 좀 생각을 해야하는 구현문제이다. 

 

# 피자는 위에서부터 들어가고 아래에서부터 쌓이기 시작하므로 반복문으로 오븐의 아래부분부터 

   확인해주면 된다. 하지만, 예제 처럼 오븐의 맨 아래 반지름이 3이고 첫번째 피자의 반지름이 3이어도

   첫번째 피자는 오븐의 맨 아래에 도달할 수 없다. 맨 아래에서 두번째 오븐의 반지름이 2이기 때문이다.

 

# 따라서, 오븐의 배열을 아래 사진과같이 재정렬해준다음 반복문을 돌려야한다. 

   오븐의 아래(마지막 인덱스)로 갈수록 반지름이 작거나 같아지도록 재정렬을 해준다.

   다음 오븐의 반지름이 현재 오븐의 반지름보다 크면 현재 오븐의 반지름으로 고정시키고

   다음 오븐의 반지름이 더 작으면 그 작은값을 그대로 넣어준다.

 

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(D-1):
    if oven[i] < oven[i+1]:
        oven[i+1] = oven[i]

# cur: 현재 우리가 확인하고자 하는 피자 인덱스
cur = 0
for i in range(D-1, -1, -1):
    # 현재피자의 반지름이 oven의 반지름보다 크면 continue 해줌으로써 i가 다음 오븐반지름 가리킴
    if pizza[cur] > oven[i]:
        continue
    
    # 현재피자의 반지름이 oven[i]의 반지름보다 같거나 작으면 cur 1증가, 다음 피자확인
    # cur이 N이면 모든피자를 오븐에 다 넣은 것이므로 i+1출력
    cur += 1
    if cur >= N:
        print(i+1)
        sys.exit(0)

# i가 0까지 왔는데 sys.exit(0)에 걸리지 않았으면 모든 피자를 넣은 것이 아니므로 0출력
print(0)

(solved.ac 티어: 골드 5)

 

# 이분탐색이나 스택을 사용해서 풀어도 된다!