trade-off table
압축은 메모리를 줄이지만 복원 근거를 지운다
정답형 구현, 1차원 압축, 복원 배열, 디버깅 로그는 서로 다른 비용을 만든다. 요구사항에 맞는 비용만 남긴다.
복원 쉬움
메모리 절약
로그 비용
| 방식 | 얻는 것 | 잃는 것 | 쓰는 순간 |
|---|---|---|---|
2D 값 + take |
정답 값과 선택 경로를 동시에 검증 | O(NC) 메모리 | 처음 기준 구현, 복원 필수 문제 |
| 1D 압축 | O(C) 메모리 | 어떤 선택이 최적인지 사라짐 | 값만 제출하고 메모리 제한이 강할 때 |
| parent / take 별도 저장 | 압축 후에도 경로 복원 가능 | 구현 복잡도와 tie-break 부담 | 값과 경로를 함께 반환해야 할 때 |
| 스냅샷 로그 | 전이식 오류를 빠르게 찾음 | 출력 시간과 해석 비용 증가 | 작은 반례로 원인을 좁힐 때 |