백준 1756. 피자 굽기

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

1756번: 피자 굽기

 

처음에 생각의 방향을 잘못 잡아 좀 오래 걸렸다.

 

우선 오븐의 깊이 D와 피자의 수 N이 둘다 최대 30만개기 때문에 단순히 위에서 부터 피자를 떨어뜨려서 쌓는 방식으로는 O(N^2)으로 불가능하다.

 

나는 이 문제를 오븐의 위에서 부터 아래로 최소값을 기록하는 방식으로 풀었다.

예를들어 오븐이 다음과 같다면 

 

5

6

4

3

6

2

3

 

위에서 부터 아래로 내려가면서 현재 까지의 최소 지름을 기록하면 다음과 같다 

 

지름, 최소

5  5

6  5

4  4

3  3

6  3

2  2

3  2

 

이 최소값이 의미하는 것은 해당 오븐 칸 위로는 적어도 최소값 이상의 지름을 갖는다는 것이다. 

이제 피자를 순서대로 아래에서 부터 채워가면 된다.

 

피자가 다음과 같다면  : 3 2 5

 

우선 지름 3의 피자의 자리는, 오븐의 아래에서 부터 탐색하면 맨 아래는 최소지름이 2이기 때문에 맨 아래 오븐칸 위로 지름이 2인 오븐이 있고, 피자의 지름은 3이기 때문에 불가능하다.

즉 아래서 부터 탐색하면서 현재 피자의 지름 보다 크거나 같은 최소값을 갖는 지점이 해당 피자가 위치 하는 지점이다.