[C++] 피자 굽기 (1756번)

피자 굽기

 

 

문제

 

월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 오묘하다. 이 오븐은 깊은 관처럼 생겼는데, 관의 지름이 깊이에 따라 들쭉날쭉하게 변한다. 아래는 오븐의 단면 예시이다.

피자 반죽은 완성되는 순서대로 오븐에 들어간다. 이렇게 N개의 피자가 오븐에 모두 들어가고 나면, 맨 위의 피자가 얼마나 깊이 들어가 있는지가 궁금하다. 이를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋째 줄에는 피자 반죽이 완성되는 순서대로, 그 각각의 지름이 주어진다. 오븐의 지름이나 피자 반죽의 지름은 10억 이하의 자연수이다.

출력

첫째 줄에, 마지막 피자 반죽의 위치를 출력한다. 오븐의 최상단이 1이고, 최하단 가장 깊은 곳이 D이 된다. 만약 피자가 모두 오븐에 들어가지 않는다면, 0을 출력한다.

예제 입력 1 복사

7 3
5 6 4 3 6 2 3
3 2 5

예제 출력 1 복사

2

힌트

---

문제풀이

문제를 어떻게 접근해야 하나 정말 많이 고민했다. 그러던 중 정렬을 이용하면 어떻게 좀 풀어볼 수 있을것 같아서 생각해 보았다.

오븐의 크기와, 오븐의 깊이를 쌍으로 갖는 벡터를 만들어 오븐의 크기를 기준으로 오름차순, 오븐의 깊이를 기준으로 내림차순으로 정렬한 뒤 밑에서 부터 탐색하면 해결이 가능할 것 같았다.

근데 이게 구현하는데 과정이 너무 헷갈려서 일일히 출력 찍어가며 한땀한땀 수정해서 구현했다.

예시를 보자.

5 6 4 3 6 2 3

을 정렬하면,

2 6

3 7

3 4

4 3

5 1

6 5

6 2

이다.

들어온 수는 3 2 5 이다.

피자를 넣을 수 있는 최대 깊이를 저장하기 위해 to 변수를 사용 하여 d로 초기화 시켜주었고, 반복문을 계속 처음부터 돌지 않게 하기 위해 from 변수를 0 으로 초기화 하여 사용했다.

 

이제 각각 순서대로 들어온 수를 처리해 보자.

맨 위부터 반복문을 돈다.

for(int j=from; j<d; j++)

맨 처음 2는 3 보다 작으므로 to의 값을 알맞게 수정한다. 3은 반드시 깊이가 2의 6보다 작은 5부터 넣을수 있다.

 to = min(to, oven[j].second-1);

다음 3, 7이다.

3은 들어온 수 3보다 크거나 같으므로 값을 넣어주어도 된다. 즉 to에 저장했던 5에 넣을 수 있다.

우선 from 값을 고쳐준다.

from = j;

다음 정답을 저장할 answer

answer = to;

다음 to는 이제 하나 들어왔으므로 1 줄여준다.

to = to-1;

만약 오븐의 크기가 모두 입력보다 작다면 반복문을 모두 통과해 버리므로 그걸 체크하기 위한 블값 변경을 해준다.

check = true;

이걸 반복하면 끝이다!

 

아래는 테스트해본 케이스들이다. (반례를 확인할 때 사용하였다.)

3 3
1 2 3
1 1 1

answer -> 1

 

5 3
6 3 4 5 1
1 2 6

answer -> 1

 

5 2
1 2 3 4 5
2 2

answer -> 0

 

5 2
2 2 3 4 5
2 3

answer -> 0

 

플고 나니 대충 280ms가 나왔다.

 

다른 사람들 풀이를 보고 정말 감탄했다.

5 6 4 3 6 2 3

가 있을경우 어차피 각 깊이 아래에는 위의 깊이의 최솟값의 크기의 피자만을 가질 수 있다. 즉 위의 오븐을 수정해버린다면, 5 5 4 3 3 2 2 가 된다!

이걸로 탐색하면 끝난다. 하하.