0에서부터 더하면서 dp를 채우는 것과, k에서부터 빼면서 dp를 채우는 것은 동일한 시간복잡도를 가집니다.

링크가 잘못됐습니다. 그리고 시간 초과 코드는 공개가 안 되어있네요.

막연한 추측이지만 dp를 0으로 초기화한 뒤 if dp[n] > 0: return dp[n]과 같이 쓰셔서 dp값이 실제 0이어도 재계산했기 때문일 거라고 생각합니다.

시간초과코드입니다.
top down방식으로 dictionary 에 계산값을 저장하였습니다

링크수정합니다

https://www.acmicpc.net/submit/2293/54978171

수정 링크 말고, 바로 옆의 언어 이름을 누르면 나오는 페이지의 링크를 주세요.

그보다 위에서도 말씀드렸지만 코드가 공개가 안 되어있습니다. 공개로 바꾸어 주세요.

dict는 평균 시간 복잡도는 O(1)이지만 기본적으로 엄청나게 느린 자료구조입니다. 시간 제한을 고려했을 때 파이썬이라면 시간 초과에 걸리는 것도 이상하지 않습니다.

PyPy3로 내면 시간 초과 대신 메모리 초과가 걸리는데, 통과하신 코드를 보니 그것도 O(nk)의 메모리를 쓰고 있어서 메모리 제한을 생각할 때 허용이 의도된 공간 복잡도가 아니지만 언어 보너스 덕분에 통과된 것으로 보입니다. 바텀 업이든 탑 다운이든 문제의 의도에서는 벗어난 풀이를 작성하신 거라고 생각됩니다.

확인해주셔서 감사합니다! 

time complexity 수준에서 차이가 아니면 통과하도록 시간 제한을 설정했어야 하는 것 아닌 가 생각했었습니다. 

말씀하신 것 처럼 dict 자료구조의 사용은 허용하지 않겠다는 의도로 보이네요.

아 글구 아래 통과한 bottom up 코드의 공간복잡도는 O(k)입니다. 시간복잡도는 O(n*k)...

감사합니다~ 다음에 또 물어보겠습니당

https://www.acmicpc.n et/source...

로직상으로는 O(k)군요. 그런데 dp = [[0]*(k+1) for _ in range(n)] 라는 문장이 한 번 실행되고 있어서 코드 자체의 공간 복잡도는 O(nk)이긴 합니다...

그리고 dict같은 건 출제자의 의도와는 아무 상관 없을 겁니다. 애초에 파이썬을 염두에 두고 만든 문제는 별로 없습니다. 대부분은 C++만이 기준이고, 파이썬은 BOJ에서 언어마다 일괄적으로 주는 보너스에 의해 풀리는 문제들이 일부 있을 뿐입니다. dict가 보너스를 받고도 제한 내에 못 들어온 건 그저 운이 없었던 거겠죠.