반응형 구간합1 백준 11659번 구간 합 구하기 4 - 스위프트(Swift) 풀이 + 그림 설명 1. 첫 번째 수부터 i번째 수 까지의 합을 저장하는 누적합 배열을 만든다. psum[i] = arr[0] + arr[1] + arr[2] + ... + arr[i] 2. arr[i] ~ arr[j] 의 구간 합은 psum[j] - psum[i - 1]과 같다. 3. i = 0인 경우 예외 처리를 해준다. 1. 첫 번째 수부터 i번째 수 까지의 합을 저장하는 누적합 배열을 만든다. psum[i] = arr[0] + arr[1] + arr[2] + ... + arr[i] 구간 i부터 j까지 반복문을 돌면서 실제로 돌면 M개의 쿼리에 대해 O(N)이 걸리는 작업을 수행하므로 총 O(NM)의 시간 복잡도를 갖는다. 이 방법으로는 N과 M이 각각 최대 10^5이므로 시간초과가 날 것이다. 구간합을 O(1)에 구.. 2022. 1. 19. 이전 1 다음 반응형
