Even Roasting

$N=1$이면 왼쪽에서 화력 $1$로 한 번 가열한다.

$N \geq 2$이면 왼쪽과 오른쪽에서 각각 화력 $N-1$로 한 번씩 가열한다. 왼쪽에서 $i$번째 고기는 첫 작업으로 $N-i$만큼, 두 번째 작업으로 $i-1$만큼 증가하므로, 최종 굽기 정도는 모두 $N-1$이 된다.

따라서 $N=1$이면 작업 횟수 $1$과 작업 $(1,1)$을 출력한다. 그 외에는 작업 횟수 $2$와 작업 $(1,N-1)$, 을 출력한다. 한 테스트 케이스의 시간 복잡도와 공간 복잡도는 모두 이다.

증명

작업을 한 번도 하지 않으면 모든 고기의 굽기 정도가 $0$이다. 최종 굽기 정도는 양수여야 하므로, 항상 한 번 이상의 작업이 필요하다.

$N=1$이면 화력 $1$인 작업 한 번으로 유일한 고기의 굽기 정도를 $1$로 만들 수 있다. 따라서 최소 작업 횟수는 $1$이다.

이제 $$라고 하자. 작업을 한 번만 수행하면, 선택한 쪽의 첫 번째 고기와 두 번째 고기의 굽기 정도는 각각 와 이 된다. 이므로 두 값은 서로 다르다. 따라서 한 번의 작업으로 모든 고기의 굽기 정도를 같게 만들 수 없으며, 최소 두 번의 작업이 필요하다.

서브태스크 1에서는 항상 $N=1$이므로 작업 $(1,1)$ 하나를 출력하면 된다. 시간 복잡도와 공간 복잡도는 모두 $O(1)$이다.

서브태스크 2에서는 완전 탐색도 가능하다. 각 작업의 방향과 $1$ 이상 $N$ 이하의 화력을 모두 시도하되, 작업 한 개로 이루어진 후보들을 먼저 확인하고, 없으면 작업 두 개로 이루어진 후보들을 확인한다. 각 후보에 대해 모든 고기의 최종 굽기 정도를 하나씩 계산하여 첫 고기의 값과 같은 양수인지 검사한다. 위에서 제시한 최적해의 화력은 항상 이하이고 작업 횟수는 두 번 이하이므로, 이 탐색 범위 안에 최적해가 존재한다. 시간 복잡도는 이고 공간 복잡도는 이다.