[백준] 1756 피자 굽기

문제 소개

---

1756피자굽기 문제는 구현문제입니다. (DP로 풀수도 있습니다.)

반죽을 완료한 순서대로 오븐에 넣습니다.

이때, 반죽의 지름이 오븐의 지름보다 작거나 같을 때만 오븐에 넣을 수 있으며 

가능한 가장 깊은 오븐에 반죽을 넣고 싶습니다.

 

피자반죽 입력 300,000 = 10^5

오븐 입력 300,00 = 10^5

이므로 이중 for문은 10^10의 크기를 가지므로 시간초과가 날 것입니다. 

또한, 피자 반죽 지름과 오븐의 지름의 순서가 중요하기 때문에 정렬을 할 수 없습니다.

 

 

문제 풀이

---

 

7 3 5 6 4 3 6 2 3 //오븐 지름 3 2 5 // 피자 반죽 지름  

 

 

 

 

 

위 예제를 가지고 예시를 들겠습니다.

먼저, 지름이 3인 첫번째 피자 반죽을 오븐의 가장 깊은 곳까지 넣을 수 있는 위치는 5번째 오븐입니다.

그 다음 오븐의 지름이 2이기 때문입니다.

 

오븐 idx	1	2	3	4	5	6	7
오븐 지름	5	6	4	3	6	2	3
피자 반죽 지름(idx)		5(3)		2(2)	3(1)

 

그 다음, 지름이 2인 피자 반죽은 첫번째 피자 반죽의 바로 앞 오븐에 넣을 수 있습니다.

 

결론적으로, 가장 깊은 오븐(가장 마지막 idx)에서 차례대로 비교를 하면 쉽게 풀 수 있습니다.

그렇게 하기 위해서 오븐 배열을 idx까지 최소 오븐 지름의 배열로 구성합니다.

 

idx	1	2	3	4	5	6	7
idx까지 최소 오븐 지름	5	5	4	3	3	2	2

 

그런 다음 오븐의 마지막 idx에서 시작하여 

현재 입력하는 피자 반죽의 지름과 비교합니다.

순서는 아래와 같습니다.

 

1) 

idx	1	2	3	4	5	6	7
idx까지 최소 오븐 지름	5	5	4	3	3	2	2

 

첫번째 피자 반죽 지름 : 3

idx : 7 일때,

피자 반죽 지름 3 > 오븐지름[7] 2 

다음 오븐으로 넘어갑니다.

 

2) 

idx	1	2	3	4	5	6	7
idx까지 최소 오븐 지름	5	5	4	3	3	2	2

첫번째 피자 반죽 지름 : 3

idx : 6일때,

피자 반죽 지름 3 > 오븐지름[6] 2 

다음 오븐으로 넘어갑니다.

 

3)

idx	1	2	3	4	5	6	7
idx까지 최소 오븐 지름	5	5	4	3	3	2	2

첫번째 피자 반죽 지름 : 3

idx : 5일때,

피자 반죽 지름 3 <= 오븐지름[5] 3 이므로 

다음 피자 반죽으로 넘어갑니다.

 

4)

idx	1	2	3	4	5	6	7
idx까지 최소 오븐 지름	5	5	4	3	3	2	2

두번째 피자 반죽 지름 : 2

idx : 4일때,

피자 반죽 지름 2 <= 오븐지름[4] 3 이므로

다음 피자 반죽으로 넘어갑니다.

 

5)

idx	1	2	3	4	5	6	7
idx까지 최소 오븐 지름	5	5	4	3	3	2	2

세번째 피자 반죽 지름 : 5

idx : 3일때,

피자 반죽 지름 2 > 오븐지름[3] 4 이므로

다음 오븐으로 넘어갑니다.

 

6)

idx	1	2	3	4	5	6	7
idx까지 최소 오븐 지름	5	5	4	3	3	2	2

세번째 피자 반죽 지름 : 5

idx : 2일때,

피자 반죽 지름 5 <= 오븐지름[2] 5 이며

마지막 이므로 현재 idx를 출력합니다.

 

 

---

소스보기