Here, we present a rigorous proof.
If you just want to know the solution, please read the editorial first.
Henceforth, we assume the side length of each square is \(1\), and that the tiles are placed on the \(xy\)-plane.

Consider the graph in which an edge is drawn between a pair of tiles \((a,b)\) if and only if they share one full side.
Then, if we place the clusters of tiles corresponding to each connected component of this graph sufficiently far apart from each other, the number of pairs sharing one full side does not change.
Also, for each connected component, we can translate and rotate it so that the following condition holds.

• Every corner of every tile is located at a lattice point (a point whose \(x\)- and \(y\)- coordinates are both integers).
  
  • If one tile is placed so that it satisfies the above condition, it can be confirmed that any tile sharing one full side with it also satisfies the condition, and so the condition can be confirmed successively, one tile after another.

This shows that there exists an optimal solution in which every corner of every tile is located at a lattice point.

Also, if there are two or more connected components, we can choose two connected components and translate one of them so that one of its rightmost sides coincides completely with one of the other’s leftmost sides, thereby increasing the number of pairs of tiles sharing one full side. Therefore, we have also proved that in an optimal solution, the \(N\) tiles form a single connected component.

Consider the bounding box (a rectangle whose sides are each parallel to the \(x\)-axis or \(y\)-axis) of the current arrangement. All corners of this bounding box are also located at lattice points.
From the way the tiles are arranged, we see that at least as much as the perimeter of this bounding box is wasted from the total perimeter of the tiles.

The area of the bounding box must be at least \(N\), and among such bounding boxes, one with the minimum perimeter is the \(k \times k\) or \(k \times (k+1)\) pattern mentioned in the editorial.
At least the perimeter amount of the above pattern must be wasted from the tiles’ perimeter, and the tile arrangement shown in the editorial actually achieves this minimum necessary amount of waste.

Therefore, the correctness of the solution presented in the editorial has been shown.