ghkdtkden93   3달 전

recursive 로 하니깐 역시 시간이 많이 걸리네요

dp로 해보려했는데 감이 잘 안잡히네요... dp로한다면 어떻게하는지

아니면 다른방법이 있는지 가르쳐주세요

0~9까지의 숫자만 입력된다는 게 힌트 같은데

중간에 음수 와 20이 초과되지않는 수는 안된다는 조건을 충족을 못시키겠네요.

onjo0127   3달 전

메모이제이션이라고 DP를 재귀적으로 풀 때 결과가 같은 함수를 중복 호출하지 않게 배열에 저장해놓는 기법이 있습니다.

memo 배열을 하나 만들어서

memo[sum][idx] 에 sum, idx를 인자로 하는 함수를 호출한 적 있는지의 여부를 저장해놓고 이미 이 함수를 호출한 적이 있다면 해당 함수를 종료하면 됩니다.

이렇게 시간을 줄여 주면 시간 내에 해결가능합니다.

댓글을 작성하려면 로그인해야 합니다.