우주선착륙은 원본 자료에 grader와 빈 스텁(init·process의 To-Do)만 공개돼 있고 검증된 통과 코드가 없다. 따라서 이 페이지는 다른 심층분석과 달리 — 라인 단위 코드 해부 대신, verify()가 정의하는 제약을 읽고 베스트 해법을 설계하며 그 정당성을 논증한다. 점수 함수가 왜 "큰 우주선 우선" 그리디를 강제하는지, 높이차 ≤ 6 제약이 어떻게 "평탄도 맵" 전처리로 환원되는지, 회전(dir)이 점수와 무관하면서도 배치 가능성을 어떻게 넓히는지를 설계 의사코드와 C++ 스케치로 제시한다. 추측이 들어가는 곳은 설계 제안으로 표시한다.
우주선착륙에는 통과 코드가 없다. 그러나 채점기 verify()와 make_tc()는 완전히 공개돼 있고, 좋은 해법의 형태는 거기서 연역할 수 있다. 먼저 점수와 제약을 정확히 적는다.
주목할 점: PENALTY = 0이고, 한 우주선의 rows/cols/dirs를 -1로 두면 verify()는 그 우주선을 건너뛴다(continue). 즉 배치하지 않아도 실패가 아니다 — 단지 그 점수를 못 얻을 뿐이다. 이것이 설계의 출발점을 바꾼다. 완전성(모든 우주선 배치)은 요구되지 않는다. 목표는 순수하게 "배치한 우주선들의 점수 합 최대화"다.
score = h·w·min(h,w)를 크기별로 펼치면 비대칭이 드러난다. 가장 작은 2×2는 2·2·2 = 8, 가장 큰 5×5는 5·5·5 = 125다. 같은 면적 한 칸을 두고 경쟁할 때 큰 우주선이 압도적으로 비싸다. 게다가 큰 우주선은 모서리 간격이 넓어 — 높이차 ≤ 6 제약을 만족할 평탄한 영역을 찾기가 더 어렵다. 즉 큰 우주선은 점수는 높고 자리는 까다롭다. 까다로운 것을 먼저, 자리가 넉넉할 때 앉혀야 한다.
그래서 베스트 해법은 두 단계로 설계된다.
-1로 남기고 다음 우주선으로.핵심 통찰은 두 단계가 서로 다른 자원을 다룬다는 것이다. 1단계는 "어디가 평탄한가"라는 지형 정보를 만들고, 2단계는 "비싼 것부터 그 정보를 소비"한다. 정보 생성과 소비의 분리는 № 01·№ 09의 설계와 같은 골격이다.
설계의 정당성을 논증하려면, 먼저 이 그리디가 만드는 해가 어떤 의미에서 "좋은가"를 정의해야 한다. 전역 최적은 보장하지 못한다 — 직사각형 패킹은 NP-난해다. 그러나 두 가지 보조정리로 "왜 큰 것 먼저인가"를 받칠 수 있다.
2단계 루프가 우주선 하나를 배치할 때마다 다음이 성립한다: 지금까지 배치된 모든 우주선의 점유 직사각형은 쌍쌍이 겹치지 않는다.
이를 유지하려면 배치 후보를 검사할 때 점유 비트맵 occupied[][]를 함께 본다 — 후보 직사각형 안에 이미 점유된 칸이 하나라도 있으면 그 후보를 기각한다. 채점기 verify()도 같은 검사를 하므로(겹침 시 return false), 이 불변식을 깨면 전체 TC가 PENALTY로 0점이 된다 — verify 실패는 break로 채점을 끝낸다.
우주선을 점수 내림차순으로 배치하면, 각 시점에서 "지금 놓는 우주선보다 비싼 우주선은 모두 이미 자리를 얻었다"는 성질이 유지된다. 따라서 어떤 우주선이 자리를 못 얻어 -1로 버려질 때, 그 우주선보다 비싼 우주선이 그 자리 때문에 밀려난 경우는 없다. 버려지는 것은 항상 남은 것 중 가장 싼 것들이다.
반대로 작은 우주선을 먼저 배치하는 순서를 생각하자. 작은 우주선 s가 어떤 평탄 영역 R을 점유했고, 나중에 큰 우주선 L이 R을 포함하는 자리만 남아 배치에 실패했다고 하자. s와 L을 바꿔 — L을 먼저 R에 놓고 s를 다른 작은 틈에 놓으면(작은 우주선은 틈이 많다), 점수 합은 score(L) − score(s) > 0만큼 증가한다.
즉 "작은 것 먼저" 순서에는 항상 점수를 높이는 교환이 존재한다. 그런 교환이 더 이상 불가능한 순서가 곧 "큰 것 먼저"다. 이것은 그리디 교환 논법의 표준 형태로, 결과 해가 전역 최적임을 보장하지는 않지만 — 순서에 관한 한 후회 없는 선택임을 보인다.
제약 ②는 미묘하다. verify()는 우주선이 덮는 직사각형의 네 모서리만 본다 — 내부 지형은 무시한다. max 네 칸 − min 네 칸 ≤ 6이면 통과다. 그러므로 "평탄한 영역"이란 영역 전체가 평평할 필요가 없고, 네 꼭짓점의 높이 편차만 작으면 된다. 이 관찰이 전처리를 가능하게 한다.
한 위치 (y1,x1)와 크기 (h,w)가 주어지면 네 모서리는 (y1,x1), (y1,x1{+}w{-}1), (y1{+}h{-}1,x1), (y1{+}h{-}1,x1{+}w{-}1)로 즉시 계산된다. 지형 높이 배열을 한 번 복사해 두면, 한 후보의 제약 ② 판정은 네 번의 배열 접근 + max/min, 즉 O(1)이다.
따라서 전처리는 사실 필요 없을 만큼 판정 자체가 싸다 — 진짜 비용은 "어느 후보를 검사할 것인가"의 탐색 횟수에 있다. 그래서 §3의 설계는 전처리보다 탐색 가지치기에 무게를 둔다.
이 문제에는 호출 비용이 없다 — process()가 끝난 뒤 verify()가 한 번에 채점한다. 따라서 "비용"은 점수 함수 그 자체이고, 설계의 비용 모델은 다음과 같다.
설계의 핵심 결정은 "한 우주선의 자리를 어떻게 찾는가"다. 100만 위치를 매번 전수탐색하면 10 TC를 시간 안에 못 끝낸다. 두 가지 가지치기를 제안한다. 설계 제안
아래는 한 우주선의 자리를 찾는 핵심 루틴의 설계 스케치다. 실제 통과 코드가 아니라 — verify의 제약에서 연역한 의사코드에 가까운 C++다.
// 우주선 i를 배치 시도. 성공하면 rows/cols/dirs에 기록하고 true.bool placeOne(int i, int H, int W) { for (int dir = 0; dir < 2; ++dir) { // 회전 두 방향 int h = dir ? W : H; // dir=1이면 90도 회전 int w = dir ? H : W; for (int y = 0; y + h <= MAP_SIZE; ++y) { for (int x = 0; x + w <= MAP_SIZE; ++x) { // ① 높이차 — 모서리 4점만, 가장 먼저 기각 int a = mapH[y][x], b = mapH[y][x+w-1]; int c = mapH[y+h-1][x], d = mapH[y+h-1][x+w-1]; int hi = max(max(a,b), max(c,d)); int lo = min(min(a,b), min(c,d)); if (hi - lo > 6) continue; // ② 겹침 — 점유 비트맵 검사 (구간합으로 O(1)화 가능) if (anyOccupied(y, x, h, w)) continue; // 통과 — 점유 표시하고 답 기록 markOccupied(y, x, h, w); rows[i] = y; cols[i] = x; dirs[i] = dir; return true; } } } return false; // 자리 없음 — i는 -1로 남는다}
dir)은 점수를 바꾸지 않는다 — verify()는 회전 후에도 spaceship_org[i].height·width·min으로 점수를 매기므로 h·w·min(h,w)는 불변이다. 회전의 가치는 오직 배치 가능성에 있다. 3×5 우주선이 가로로는 안 들어가는 평탄대(帶)에 세로로는 들어갈 수 있다. 그래서 설계는 회전 두 방향을 모두 시도하며, 한쪽이라도 들어가면 그 자리를 쓴다. anyOccupied는 2차원 구간합(prefix sum)으로 O(1)에 만들 수 있으나, 점유가 갱신될 때마다 구간합을 다시 짓는 비용이 있어 — 격자가 듬성할 때는 단순 스캔이 더 쌀 수 있다. 설계 제안
순진한 전수탐색은 우주선당 2 · 10⁶ 후보, 10⁴ 우주선, 10 TC로 2×10¹¹ — 시간 초과다. 그러나 높이차 조기 기각이 거의 모든 후보를 첫 줄에서 제거한다. 무작위 지형에서 모서리 4점이 모두 폭 6 안에 드는 확률은 작고(대략 수 % 수준), 첫 평탄 자리를 만나면 즉시 return하므로 — 우주선당 기대 후보 수는 위치 공간을 끝까지 훑지 않고 훨씬 일찍 끝난다. 격자가 채워질수록 큰 우주선은 자리를 못 찾아 일찍 실패하고, 작은 우주선은 틈이 많아 금방 자리를 찾는다. 실측 없이 정확한 상수는 말할 수 없으나, "조기 기각 + 첫 적합 즉시 채택"의 조합이 시간 예산 안에 드는 것이 설계의 전제다. 설계 제안
한 TC에 우주선 10,000개가 있다. 크기는 2~5 균등이므로 평균 점수는 대략 — h,w가 각각 {2,3,4,5} 균등일 때 E[h·w·min(h,w)]는 약 40 안팎이다. 10 TC 누적이면 우주선이 모두 배치될 때의 점수 상한은 대략 10 · 10⁴ · 40 = 4×10⁶ 규모다. PASS 기준 3,000,000은 그 상한의 약 75%다.
이 비율이 설계에 주는 메시지는 분명하다 — 모든 우주선을 배치할 필요는 없지만, 큰 우주선 대부분은 반드시 앉혀야 한다. 큰 우주선(5×5 = 125점)을 충분히 못 앉히면 75%에 못 미친다. 그래서 §1의 "큰 것 우선" 순서는 단순한 휴리스틱이 아니라 PASS의 필요조건에 가깝다.
한 우주선이 placeOne에서 실패해 -1로 남아도 — verify()는 그 우주선을 건너뛸 뿐 전체를 실패시키지 않는다(PENALTY = 0). 따라서 그리디는 "되돌리기(backtracking)" 없이 진행해도 안전하다. 한 우주선의 실패가 다른 우주선의 점수를 깎지 않는다.
이것이 설계를 단순하게 만든다. 직사각형 패킹의 일반형은 백트래킹이 필요하지만, 이 문제는 "놓을 수 있으면 놓고, 없으면 포기"라는 단조 진행만으로 충분하다 — 포기에 페널티가 없기 때문이다.
§3의 스케치는 첫 적합이다 — 들어가는 첫 자리를 즉시 쓴다. 대안은 최선 적합 — 모든 가능한 자리를 보고 "가장 빈 공간을 적게 낭비하는" 자리를 고른다. 직관적으로 best-fit이 더 좋아 보이지만, 두 가지 이유로 first-fit을 권한다. 설계 제안
다만 스캔 순서를 살짝 흔드는 것 — 예컨대 큰 우주선을 격자 중앙 근처부터, 작은 우주선을 가장자리부터 탐색 — 은 평탄 영역을 큰 우주선에 양보하는 효과가 있어 검토할 가치가 있다.
| 전략 | 겹침안전 | 점수 경향 | 시간 | 평가 |
|---|---|---|---|---|
| 입력 순서대로 첫 적합 | 안전 | 중간 | 빠름 | 작은 우주선이 평탄대를 선점 — 큰 우주선 손해 |
| 작은 우주선 우선 | 안전 | 낮음 | 빠름 | Theorem 1 위배 — 점수 높은 교환이 항상 남음 |
| 완전 직사각형 패킹 최적 | 안전 | 최대 | 불가 | NP-난해 — 10⁴ 우주선 규모에서 시간 초과 |
| 큰 우주선 우선 + 회전 + 높이차 조기기각 | 안전 | ≥ 3,000,000 목표 | 중간 | 비싼 것 먼저 + 자리 까다로운 것 먼저 + 빠른 판정 |
표의 구조는 §1의 분해를 비춘다. 겹침 안전은 점유 비트맵만 지키면 어느 전략이든 공짜로 얻는다(Invariant). 진짜 경쟁은 점수에서 벌어진다. 입력 순서·작은 것 우선은 Theorem 1의 교환 논법으로 항상 개선 여지가 남고, 완전 패킹 최적은 NP-난해라 10,000개 규모에서 불가능하다. 따라서 "큰 것 우선 그리디 + 회전 + 높이차 조기 기각"이 — 통과 코드가 없는 상태에서도 verify의 제약으로부터 연역할 수 있는 현실적 최선이며, Theorem 1이 그 순서의 후회 없음을 받친다.
verify()는 dirs[i]==1일 때 y2 = y1 + width - 1, x2 = x1 + height - 1로 — height와 width를 맞바꿔 점유 직사각형을 계산한다. 배치 검사에서 회전을 적용하면서 채점기와 같은 교환을 하지 않으면, 검사한 자리와 실제 점유 자리가 어긋나 겹침 PENALTY를 맞는다.
make_tc()는 모든 우주선의 rows/cols/dirs를 -1로 초기화한다. 자리를 못 찾은 우주선은 이 -1을 그대로 두어야 verify()가 건너뛴다. 실수로 0 등을 써넣으면 (0,0)에 배치된 것으로 해석돼 겹침·경계 위반을 일으킨다.
y + h - 1이다. 루프 조건은 y + h ≤ MAP_SIZE(끝 인덱스 y+h-1 ≤ 999)여야 한다. -1을 빼먹으면 한 칸 넘쳐 verify()의 경계 검사(y2 ≥ MAP_SIZE)에 걸린다.
h·w가 아니라 점수 h·w·min(h,w)여야 한다. 예: 2×5(면적 10, 점수 20)와 4×4(면적 16, 점수 64)는 면적 순과 점수 순이 다르다. 그리디가 진짜로 최적화하는 양은 점수다.
이 문제는 통과 코드가 없으므로 측정된 SCORE를 제시할 수 없다. 대신 채점기의 판정 구조를 명시한다. verify()가 한 우주선이라도 제약 ①②③을 어기면 SCORE = PENALTY(0) 후 break — 전체 0점이다. 모두 통과하면 배치된 우주선 점수 합이 누적되고, 10 TC 합이 3,000,000 이상이면 PASS다.
verify()·make_tc()로부터 연역한 설계다. placeOne() 스케치는 컴파일·실측을 거치지 않았으며, Theorem 2의 시간 복잡도는 무작위 지형의 평탄 영역 분포에 대한 추정에 의존한다. "큰 우주선 우선"과 "회전 두 방향"은 verify의 제약에서 안전하게 연역되지만, 정확한 SCORE는 실제 구현·실행으로만 확정된다.