[Algorithm] 백준 11659번 : 구간 합 구하기 4 (C++)

문제 링크 : https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

---

[문제]

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합하는 프로그램을 작성하시오.

[입력]

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야하는 구간 i와 j가 주어진다.

[출력]

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

[제한]

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

[알고리즘 분류]

• 누적 합

---

[해설]

이 문제는1  ≤ N ≤ 100,000 와 1 ≤ M ≤ 100,000 라는 제한을 두고있어 단순히 반복문을 이용해 각 입력에 대해 계산을 진행해 출력하도록 한다면 시간초과가 일어나게 된다.
따라서, 입력을 받고 계산을 진행하는 것이 아닌, 이미 계산이 되고 난 후의 값을 배열에 저장해 출력하는 방법을 이용해야한다.
이를 위해서 문제가 원하는 것을 잘 생각해보아야 한다. 우선, 문제가 원하는 것은 특정 범위의 '누적 합' 인데, 이는 배열에 입력되고 난 후에 구할 수도 있지만, 입력과 동시에 누적시킬 수 있다는 것을 알아야한다.

즉, 원래 배열의 i인덱스 에 넣고자하는 값에 가지고 이전 인덱스 i-1의 값을 더하여 i인덱스에 저장하는 과정을 반복한다면 배열에는 자연스럽게 값이 누적되어 저장된다는 말이다.

또한, 여기에서 특정 범위 내에서의 누적 값을 구할 때는 가장 끝에 누적된 값 j에서 누적이 시작되는 범위인 i 이전까지의 누적값을 빼면 된다.

[정답 코드]

#include<ios>
int main(){
  int N,M,i,j,A[100000];
  scanf("%d%d",&N,&M);
  for(int a=1;a<=N;a++){
    scanf("%d",&A[a]);
    A[a]+=A[a-1];
  }
  for(int a=0;a<M;a++){
    scanf("%d%d",&i,&j);
    printf("%d\n",A[j]-A[i-1]);
  }
}

[결과]