§ 1문제 정의
‘평평한’이 무엇인지가 중요하다 — 네 모서리만 본다. 모서리 4점의 max - min ≤ 6이면 합법. 가운데가 얼마나 울퉁불퉁한지는 무시한다.
큰 우주선부터 두는 것이 점수 함수상 유리하다 — 5×5는 125, 2×2는 8이다. 같은 면적이면 정사각형이 더 비싸다(짧은 변이 가중치).
방향(rotation)은 dir = 0 또는 1로 90도 회전 가능. 같은 자리에 서로 다른 우주선이 겹치지 않게 occupied 그리드로 표시하며 진행.
정사각형이 더 비싸다. 5×5 자리를 찾으면 무조건 거기에 놓아라.
§ 2예제 시각화 — 12×8 미니맵 + 4척 착륙
FIG. 8 — corner-tilt validation, occupy & advance
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
process(rows[], cols[], dirs[]):
sort ships by area × min(h,w) DESC # 큰 우주선 먼저
occupied = grid[1000][1000] = false
for ship in sorted:
for (y, x) in scan order:
for dir in [0, 1]:
h, w = (ship.h, ship.w) if dir==0 else (ship.w, ship.h)
if y+h-1 >= 1000 or x+w-1 >= 1000: continue
if any cell in [y..y+h-1][x..x+w-1] is occupied: continue
corners = [map[y][x], map[y][x+w-1],
map[y+h-1][x], map[y+h-1][x+w-1]]
if max(corners) - min(corners) > 6: continue
mark occupied
save (y, x, dir) → SCORE += h*w*min(h,w)
break