cocogod   5달 전

재귀로 n 번 돌립니다.

이때 그전수보다 2배 커야하니까 for문에 초기값을 2배 크게하였습니다.

그후 하나씩 재귀호출을 합니다.

이때 메모라이징하여 다음에 찾을것을 저장하였습니다.

틀렸다고 뜨는데 잘못 짠건가요.. ㅠㅠ

zlzmsrhak   5달 전

답을 계산한 뒤에 dp 배열을 -1로 초기화시켜야 할 것 같습니다.

cocogod   5달 전

zlzmsrhak 이제  틀리지않고 시간초과 가 뜹니다 ㅠㅠ ...

메모라이징 잘한거 같은대 아닌가요?


zlzmsrhak   5달 전

음.. 생각보다 테스트케이스가 많았나 보네요.

모든 (n, m) 쌍에 대하여 답을 O(10 * 1000) 으로 구해야만 시간초과가 나지 않을 것 같습니다.

예를 들면, dp[n][m] = (숫자가 n개, 숫자 제한이 m일 때의 답)으로 정의하면 됩니다.

지금 dp table의 값은 m이 바뀌면 바뀌기 때문에 식을 수정해야 합니다.


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