[백준] 2632 피자 판매

---

피자는 A 종류 이거나 B 종류이거나 A와 B 혼합하여 판매할 수 있다. 그리고 한 종류의 피자 조각 을 2개 이상 판매할 때 그 조각들은 반드시 연속해야한다.

 

'조각들이 연속해야한다'는 부분에서 A와 B 각각 누적합을 구해야함을 알 수 있다. 그리고 구해진 누적합을 이분탐색을 통해 고객이 원하는 피자의 크기를 구할 수 있다.

 

누적합 구하기

피자는 원형이기 때문에 순환 배열(Circular Array) 누적합을 구해야한다. start(front), end(rear) 포인터를 사용해야한다.

start와 end 포인터를 한 칸씩 이동하면서 누적합을 구한다. 단 start 포인터가 다시 0이 되면 종료한다. 

 

start에서 end까지 모든 수의 누적합이 구매자가 원하는 크기 보다 작거나 같을 경우 조각의 개수 만큼 중복된다.

따라서 start ~ end-1까지 누적합을 구하고 마지막에 start ~ end까지 누적합이 구매자가 원하는 크기 보다 작을 경우 누적합 배열에 포함 시킨다.

 

이분 탐색

left, right 투 포인터를 사용한다. left는 A 피자의 첫 번째 누적합 원소를 가리키는 포인터이다. right는 B 피자의 마지막 누적합 원소를 가리키는 포인터이다. 

 

Python

 

Java