DP 처리 흐름

DP 구현·복원 비교

2차원 표는 설명과 복원에 강하고, 1차원 압축은 메모리에 강하다. take 또는 parent 기록은 그 사이의 비용을 명시한다.

정답형 구현

1
dp[i][c] + take[i][c]

전체 상태를 남겨 전이식, 최종값, 선택 기록을 같이 검증한다.

보존 정보 값, 선택 여부, 행별 스냅샷

동일 입력 검증

2
best2d == best1d

작은 반례와 손계산 표로 압축 전후 값이 같은지 먼저 고정한다.

복원 필요성 최댓값 37, 선택 합계 5

공간 압축

3
dp[c] from high to low

역순 순회로 중복 선택을 막고, 값만 필요하면 공간을 O(C)로 낮춘다.

손실 정보 행 번호, 선택 원인, parent

복원과 로그

4
walk parent or take

경로 요구가 있으면 별도 기록을 남기고, 디버깅은 작은 입력에 집중한다.

확인 대상 동점, 용량 갱신, 인덱스

저장 방식별 상충 관계

방식
값 검증
공간
복원
2차원 DP
강함
O(NC)
쉬움
1차원 DP
강함
O(C)
약함
take/parent
추가 검증
기록 비용
가능