kkw564   8년 전

제가 만든 알고리즘 말고 더 간단한 알고리즘이 있나요??

시간초과 뜨길레 전역변수 잡아봤는데도 시간초과네요..

시간초과가 나올 거라곤 생각도 못했는데

이건 순서변경도 아니고 그냥 더하는건데 시간초과가 떠버려서 당황스럽네요..


baekjoon   8년 전

ㄴㅔ 그냥 더하는 시간이 총 N*M이 걸려서 너무 느려요.

kkw564   8년 전

혹시 이런것도 자료구조를 이용한 덧셈같은걸 해야되는건가요..?

제가 아직 자료구조에 대해서 잘모르고 기본으로 문제들을 접하고있어서요.

baekjoon   8년 전

prefix sum을 이용해야 합니다.

s[i] = a[1] + ... + a[n]

이라고 하면

a[i] + ... + a[j] = s[j] - s[i-1]

로 구할 수 있습니다.

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