[SWEA] 3752. 가능한 시험 점수 -DP

이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn

완전 탐색과 DP를 적용하는 방법 말고는 다른 방법이 떠오르지 않네요...

이 문제는 DP를 적용했을 때 어느 정도의 시간 복잡도일지 계산하는게 너무 어려워서

선뜻 DP를 적용하기 고민됐던것 같네요.

DP를 설계할때 핵심이 됐던 함수

는 현재까지 계산한 점수와, 현재 위치를 인자로 받아서

앞으로 더 만들 수 있는 새로운 수를 반환하게 했습니다.

이 DP를 위한 cache입니다 n이 100이하고 각 숫자가 100이하 이므로 최대 num은 10000 이고, pos의 최대값은 99가 되겠죠.

http://colorscripter.com/s/GDvk0bt