responsibility split
정답 값, 압축, 복원, 디버깅은 서로 다른 책임이다
각 책임을 분리해 두면 값 배열을 줄이더라도 복원과 오류추적에 필요한 정보를 실수로 지우지 않는다.
answer
memory
restore
debug
정답 값
기준 DP 표
dp[i][c]로 정답을 먼저 맞추고 작은 입력에서 손계산과 비교한다.
메모리
압축 배열
이전 행만 필요하면 dp[c]로 줄이되 순회 방향을 명시한다.
복원
선택 근거
take나 parent를 남겨 최종 상태에서 선택 경로를 역추적한다.
제출 전 질문: 값 배열을 지워도 선택 이유를 말할 수 있는가? 아니라면 압축보다 복원 정보를 먼저 설계한다.