ペンギンの居ないマスが何個連続しているかに注目します． 最初，空きマスの個数が，\(x_0,x_1,\cdots,x_N\) だったとします． \(x_0\) はペンギン \(1\) より左にある空きマスの個数，\(x_N\) はペンギン \(N\) より右にある空きマスの個数，\(x_i\) (\(1 \leq i \leq N-1\)) はペンギン \(i\) とペンギン \(i+1\) の間にあるマスの個数です．

ペンギンを動かす操作で \(x\) がどう変化するか考えると，ある \(i\) と \(j=i+1\) or \(i-1\) を選び，\(x_j+=x_i,\ x_i:=0\) という操作であるとわかります．

終状態における空きマスの個数を \(y_0,y_1,\cdots,y_N\) とします． \(y_i\) は，\(x_i\) の連続するいくつかの値を一つにまとめ，それを適宜移動させたもの，という形になっていなくてはなりません． \(y_i>0\) のとき，\(y_i\) の元になった \(x\) の値の範囲 \([l,r]\) を求め，それを \(i\) に移動させてくるコストを考えると，最小で \(\mathrm{max}(i-l,0)+\mathrm{max}(r-i,0)\) 回の操作が必要だとわかります． また，この最小回数が十分であることもわかります． （どの \(y_i\) に値を集めるかの順番を考慮する必要がありますが，結局，どの \(i\) についても最小回数で目標を達成する操作列があります）

以上の操作は \(O(N)\) で実装できます．