무식한 2차원 배열 DP 파이썬으로 시간 초과가 나서 똑같은 코드로 pypy로 ac를 받았습니다.

그리고 파이썬으로 통과한 분들이 계신지 확인을 해 보니, 거의 유사한 방식에서 슬라이딩 윈도우 형태를 가미해서 

통과를 하셨더라구요.

여기서 궁금증이 하나 생긴건은

1. 큰 배에 대한 인덱싱에 유의미한 시간이 더 필요 한가요?

제 배열을 최대 4001*4001이 됩니다.

그분의 배열은 2*4001의 배열로 해결을 하셨습니다.

arr[3000][1]과 arr[1][1]에 조회의 속도차가 크게 날까요?

인덱싱은 O(1)로 생각하고 있어서 간과하고 있었는데,

오히려 배열한 줄을 복사하는 추가 연산이 들어 갔음에도 다른 분의 코드는 시간안에 통과가 되고, 제 코드는 시간초과가 났습니다.

2. 파이썬에서 함수로 전체 코드를 덮으면 사용하는 메모리의 총량이 추가 되나요? 아니면 BOJ에서 스택과 힙의 메모리 계산이 별도로 되는 걸까요?

어느 분이 말씀 하실 때, 파이썬의 코드를 함수로 wrap하면 더 빨라 진다길래 제 본래 코드를 main() 함수로 쌓아서 제출을 했더니 메모리 초과가 나았습니다. 일반적으로는 pypy가 파이썬에 비해 메모리를 더 잡아 먹고 속도는 더 빨리 돌아갔는데요. pypy에서는 메모리 초과가 아닌 ac를 받았음에도 같은 코드의 파이썬은 시간 초과가 아니라 메모리 초과가 나왔습니다. 단순 pypy가 메모리를 많이 먹으니 메모리의 제한이 파이썬보다 높게 설정되서 통과 된 것이라면, 이건 재체점이 필요한 내용일 듯 합니다.