[백준] 1756 피자 굽기 - 골드 5

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• 이분 탐색, 구현

---

1. 문제 설명

 

위 그림처럼 생긴 오븐이 존재할 때 해당 오븐에 피자 도우를 쌓아 나갑니다.

 

마지막 피자 도우를 오븐에 넣었을 때 현재 오븐의 깊이를 구하는 문제 입니다.

---

2. 접근 방식

 

우선 힌트를 보고 어느정도 방법이 생각났습니다.

 

가장 먼저 도우 작업이 완료된 도우의 크기가 3 입니다.

 

그럼 이 도우를 놓기 위해선 바닥에 놓거나 혹은 이 도우보다 오븐이 더 작은곳이 있다면 그 위에 올리면 됩니다.

 

즉 현재 도우의 크기를 기준으로 오븐의 바닥부터 놓을 수 있는 곳을 탐색할 때, 현재 도우보다 오븐이 더 넓어지는 순간 해당 위치에 도우를 놓으면 될 것 같습니다.

 

근데 한가지 문제점이 이 오븐은 바닥이 3이고 그 위가 2라서 바닥부터 탐색을 하는 경우 현재 도우의 크기와 바닥의 크기가 동일하니 잘못 도우를 놓을 수 있습니다.

 

따라서 오븐의 크기를 내림차순으로 정렬해줄 필요가 있습니다.

 

내림차순도 그냥 하면 오븐의 크기가 뒤죽박죽이 되버리니 현재 위치를 기준으로 다음 위치가 더 큰 경우 다음 위치를 현재 위치의 크기로 바꿔줍니다.

 

무슨 말이냐, 도우의 크기를 3, 현재 탐색 위치의 크기가 2,  그 다음 위치가 3 이라고 가정해 보겠습니다.

 

현재 위치가 2이니 그 다음 위치 3에는 어차피 도우를 놓을 수 없습니다.

 

도우가 크기가 3이라서 2의 크기를 가진 오븐을 통과할 수 없기 때문입니다.

 

그럼 그 아래쪽이 더 커봤자 의미가 없으니 그 아래쪽 크기를 현재 위치의 크기랑 똑같이 맞춰주는 겁니다.

 

그렇게 해도 탐색에는 지장이 없기 때문입니다.

 

그 후 바닥부터 탐색을 실시하며 오븐에 도우를 놓는 모든 경우를 찾아주면 될 것 같습니다.

---

3. 코드

import sys
input = sys.stdin.readline

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

# 오븐 크기 재정렬
# 오븐의 현재위치 크기보다 아래에 있는 크기가 더 크다면 거기까지 들어가도 현재 크기만큼의 피자밖에 통과 못하니 더 좁은 크기로 변경
# 오븐의 크기를 내림차순 정렬과 동일
for i in range(D-1):
    if oven[i] < oven[i+1]:
        oven[i+1] = oven[i]

# 피자의 인덱스, 오븐의 인덱스
pizza_index = 0
oven_index = D - 1

# 오븐의 가장 아래쪽이 가장 좁은 부분이니 오븐의 가장 아래쪽 부터 탐색
while oven_index >= 0:

    # 현재 피자의 크기보다 오븐의 크기가 큰 경우 여기에 피자를 놓을 수 있음
    if pizzas[pizza_index] <= oven[oven_index]:
        
        # 피자 인덱스 증가
        pizza_index += 1

        # 만약 마지막 피자인 경우 종료
        if pizza_index == N:
            break
    
    # 오븐이 더 작은 경우 오븐 조금씩 위로 올라가기
    oven_index -= 1

# 모든 오븐을 탐색했는데 오븐에 피자를 다 놓지 못한경우 0 출력 아닌 경우 현재 오븐의 깊이 출력
if pizza_index < N:
    print(0)
else:
    print(oven_index + 1)

---

[코드 설명]

# 오븐 크기 재정렬
# 오븐의 현재위치 크기보다 아래에 있는 크기가 더 크다면 거기까지 들어가도 현재 크기만큼의 피자밖에 통과 못하니 더 좁은 크기로 변경
# 오븐의 크기를 내림차순 정렬과 동일
for i in range(D-1):
    if oven[i] < oven[i+1]:
        oven[i+1] = oven[i]

 

오븐의 크기를 재정렬하는 코드입니다.

 

현재 위치를 기준으로 다음 위치가 더 큰 경우 다음 위치의 크기를 현재 위치의 크기로 변경해주는 겁니다.

 

그럼 예제 입력을 기준으로 살펴보면

 

5 6 4 3 6 2 3 이 입력되었다면 이걸 오븐의 재정렬을 실시하면 다음과 같이 됩니다.

5 5 4 3 3 2 2 가 됩니다.

 

왜냐 현재 위치보다 다음 위치가 더 커봤자 어차피 의미가 없기 때문입니다.

---

# 피자의 인덱스, 오븐의 인덱스
pizza_index = 0
oven_index = D - 1

# 오븐의 가장 아래쪽이 가장 좁은 부분이니 오븐의 가장 아래쪽 부터 탐색
while oven_index >= 0:

    # 현재 피자의 크기보다 오븐의 크기가 큰 경우 여기에 피자를 놓을 수 있음
    if pizzas[pizza_index] <= oven[oven_index]:
        
        # 피자 인덱스 증가
        pizza_index += 1

        # 만약 마지막 피자인 경우 종료
        if pizza_index == N:
            break
    
    # 오븐이 더 작은 경우 오븐 조금씩 위로 올라가기
    oven_index -= 1

# 모든 오븐을 탐색했는데 오븐에 피자를 다 놓지 못한경우 0 출력 아닌 경우 현재 오븐의 깊이 출력
if pizza_index < N:
    print(0)
else:
    print(oven_index + 1)

 

이분 탐색을 실시하며 정답을 출력해 주었습니다.

 

오븐은 바닥부터, 피자도우는 가장 먼저 만들어진 것 부터 탐색이 시작되어야 합니다.

 

따라서 pizza_index 는 0, oven_index는 바닥이 D - 1 로 설정해 주었습니다.

 

현재 바닥에 피자 도우가 들어가지 않는다면 오븐의 위치를 한 칸씩 위로 올려주고

 

현재 오븐의 위치에 피자 도우가 들어간다면 다음 피자를 꺼내옵니다.

 

꺼내 왔는데 마지막 피자인 경우 탐색을 종료하고 출력을 실시합니다.

 

N은 피자의 개수를 의미하는데 현재 pizza_index가 N보다 작다, 즉 모든 피자가 오븐에 들어가지 않았다면 0을 출력

아니라면 현재 오븐의 깊이 -> 배열의 인덱스 이므로 + 1 해서 출력해 주었습니다.

---

4. 결과

---

[회고]

이번 문제는 구현 문제인데 조건이 좀 특이한 문제 였습니다.

 

처음 시간 초과는 우선 모든 경우의 수를 구해보았습니다.

 

당연히 30만 x 30만 탐색을 실시하니 시간 초과가 발생할 건 알았는데 현재 구현이 제대로 이루어져서 시간 초과가 발생하는지

혹은 틀렸는지를 판단해보기 위해 시도해 보았습니다.

 

첫 시도에서는 오븐의 크기를 정렬하지 않고 중첩 반목을 이용해서 시간 초과가 발생했습니다.

 

당연히 시간 내에 통과하려면 1번의 반복에서 모든 경우의 수를 찾아야 했기에 이분 탐색을 실시해야 겠다 까지는 생각이 났는데

 

오븐의 크기 정렬을 생각하지 못하고 있었습니다.

 

막상 이분 탐색으로 탐색을 하려고 해도 바닥부터 탐색하는 경우 바닥의 크기가 크면 소용이 없는데... 하면서 20분을 고민했던것 같습니다.

 

그러다 음료수를 마시는데 음료수를 보고 아이디어가 떠올랐습니다.

 

코카콜라 제로 500ml 페트 마시고 있었는데 페트 입구는 좁은데 아래쪽은 넓은걸 보고 오 이거? 오븐의 형태랑 비슷한데 라는 생각이 들었다가 어 이거 아래가 커봐야 의미가 없겠구나 어차피 입구가 크기가 작으면 피자 도우가 안들어 가겠네 라는 생각이 떠올랐고

 

오븐의 크기를 재정렬 해주면 되겠다 까지는 아이디어를 떠올릴 수 있었는데, 그 다음 구현이 문제였습니다.

 

음 결국 입구가 제일 커야하니 더 큰 크기를 입구로 맞춰야 하나? 싶었다가 아 아래로 갈수록 점점좁아지는 깔데기 형태로 하면 되겠네 라고 생각해서 오븐의 크기를 재정렬 할 수 있었습니다.

 

아이디어 떠올리기가 어려웠고 구현자체는 그렇게 빡센 구현이 아니었다고 생각합니다.