빼빼로 시식회

$N=2$이면 인접한 두 길이의 합이 하나뿐이므로 차이는 $0$이다. $N\geq3$에서 모든 합이 같다면 $P_1+P_2=P_2+P_3$이므로 $P_1=P_3$이 되어 모순이다. 따라서 최솟값은 적어도 $1$이다. $m=\lfloor(N+1)/2\rfloor$로 놓고 $m,m+1,m-1,m+2,m-2,\ldots$ 순서로 범위 안의 수를 출력한다. 모든 수가 한 번씩 나오며 인접한 합은 $2m$과 $2m+1$ 중 하나이다. 따라서 하한을 달성한다. 시간 복잡도는 $O(N)$, 추가 공간은 $O(1)$이다. 첫 서브태스크는 모든 순열을 열거하는 $O(N!N)$ 풀이로 해결할 수 있다.

Solution written by GPT6.1