2차원 리스트 절반만 사용해서, i~j 값을 한번에 다 구하고 시작을 했습니다.

그때 그때 계산하면 시간 초과에서 못 벗어나더라구요...

힌트 있으실까요 ㅠ,ㅠ

미리 감사드립니다.

fail   11달 전

1부터 10만까지의 합은 5000050000 입니다. 이차원 리스트에 이만큼의 정보를 저장한다면 너무나도 많은 메모리를 차지하게 될 것입니다.

그리고 값을 저장하기 위해 5000050000번의 연산을 하게 될텐데 이 또한 시간이 허락해주지 않습니다.

a-b의 구간합은 (처음부터 b까지의 누적합) - (처음부터 a까지의 누적합) 이라고 다시 표현할 수 있습니다.

따라서 전체적인 누적합 배열 하나만 만들게 된다면 구간합을 쉽게 구할 수 있습니다.


도움 감사합니다.

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