[AC] 2632 피자판매

출처 : https://www.acmicpc.net/problem/2632

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2632.cpp

이 문제는 좀 괜찮은 문제같다. 어렵지 않으면서 이것저것 생각할것도 조금 있고, 코딩도 상당히 해야한다.

문제를 살펴보면 피자의 크기의 최대는 2백만이고, 피자조각의 최대크기는 1000조각이다.

그럼 n^2(1000^2)까지는 계산이 허용된다는 말이니 여기에 중점을 두고 생각해보자.

그리고 주목해야할 부분이 바로 피자의 조각을 뺄때는 연속으로만 뽑을 수 있다고 한다.

그럼 각 피자당 뽑을수있는 경우의수는 매우 제한적이게 될 것이다. 

먼저 피자가 총 2조각으로 이루어져있다면 1조각짜리 2개 2조각짜리 1개로 구성되어 3개이다.

그리고 총 3조각이라면 1조각짜리 3개 2조각짜리 3개 3조각짜리 한개여서 총 5조각이다. 

수식으로 구해보면 n*(n-1)+1이 성립한다.

그럼 최대 인풋이 1000이니 식을 구해보면 대략 100만이 조금 안되는 값이 나온다. 그렇다면 배열에 모든 경우의수를 담아볼수있다.

피자는 2개로 구성되어있으니 총 2백만개의 배열이 필요하다.

그렇게 하여 각 피자당 구할수있는 모든 조각의 크기를 미리 구해놓는다. 그리고 한개의 피자에서 한개의 조각을 꺼냈을때 남은피자에서 n-사용한 조각을 하면 현재 필요한 조각수를 알수있으므로 그 조각수가 나오는 경우가 있는지 살펴보면 된다.

즉!! 이진탐색문제이다. 그러므로 당연히 정렬이 필요하다. 미리 구해둔 모든 조각의 크기를 정렬하고 구하고자 하는 값을 찾아보면 된다. 이때 중복이 있을수 있으니, 중복에 대한 경우를 체크하도록 한다.

그리고 하나더

시간단축을 위해 이진탐색에서 찾을 값이 음수이거나, 최대크기보다 큰값이라면 구할수 없으니 종료를 한다.

뿐만아니라 나는 나중에 깨달았지만 미리 idx배열을 1부터 시작한다면 즉 0인값을 넣어놓는다면 하단부분 계산파트에서 0인경우를 나처럼 따로 처리하지 않아도 된다. 그럼 코드가 더 간략해질것이다.