11659번 - 구간 합 구하기 4
제가 만든 알고리즘 말고 더 간단한 알고리즘이 있나요??
시간초과 뜨길레 전역변수 잡아봤는데도 시간초과네요..
시간초과가 나올 거라곤 생각도 못했는데
이건 순서변경도 아니고 그냥 더하는건데 시간초과가 떠버려서 당황스럽네요..
ㄴㅔ 그냥 더하는 시간이 총 N*M이 걸려서 너무 느려요.
혹시 이런것도 자료구조를 이용한 덧셈같은걸 해야되는건가요..?
제가 아직 자료구조에 대해서 잘모르고 기본으로 문제들을 접하고있어서요.
prefix sum을 이용해야 합니다.
s[i] = a[1] + ... + a[n]
이라고 하면
a[i] + ... + a[j] = s[j] - s[i-1]
로 구할 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
kkw564 8년 전
제가 만든 알고리즘 말고 더 간단한 알고리즘이 있나요??
시간초과 뜨길레 전역변수 잡아봤는데도 시간초과네요..
시간초과가 나올 거라곤 생각도 못했는데
이건 순서변경도 아니고 그냥 더하는건데 시간초과가 떠버려서 당황스럽네요..