동적계획법. [11052]

[1. 문제 설명]

[2. 풀이 접근]

나에게는 정답률에 비해 다소 까다로웠던 문제...

완전 탐색 풀이부터 접근...

메모이제이션

현재가지 m 개 샀다고 하자
이번에는 l 번째 pack 을 사는 경우를 따져본다.
즉, 메모이제이션 해야하는 팩터는 m 과 l 로 결정 할 수 있다.
첫번째, 이번 pack 을 사지 않고, 다음 pack 부터 사는 경우=> 캐시를 최대 값으로 업데이트
두번째, 이번 pack 을 여러번 사고, 이 금액과 다음 pack 을 사는 재귀 결과의 합 => 캐시를 최대 값으로 업데이트
=> 이 부분을 구현하는데 좀 오래걸렸는데,, 왜 그랬을까?
=> 이 외에도, 완전 탐색에서 메모이제이션을 적용하는 과정에서 내 생각대로 되지 않은 부분이 꽤 많았다.

메모이제이션 시 실수 한 혹은 유념할 부분.

완전 탐색에서 재귀의 끝까지 가서 한가지 경우를 체크하고,
이 과정을 메모이제이션 할 때,
메모이제이션의 결과가 잘못 저장 될 수 있다.
=> 잘못 저장 된 결과를 나중에 다시 사용하다 보니, 전체 결과가 이상해짐.
완전 탐색 -> 메모이제이션을 적용 할 때는 최대한 빨리 끝낼 수 있는 부분(답을 바로 결정 할 수 있는 부분이 먼저 오도록 해야 한다.
=> 아래 코드에서 첫번째/두번째 기저사례를 지우면 제출 시 틀린다.

다른 풀이 (반복적 동적계획법을 사용한 풀이...)

[3. 코드]

test_kernelv2