개발자 퉁이리

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 누적 합 ⊙ 문제 접근 과정 누적 합 문제다. 처음엔 구현으로 풀라고 했다. 이중 for문을 사용하니 시간 복잡도가 O(N^2)이고 N과 M이 100,000까지라 시간 초과를 만날 수 있었다. 누적 합 문제의 해결법은 값을 배열에 넣고, 그 배열의 값들을 누적합 값으로 갱신시켜주어 index로 접근하여 구해주면 된..