문제
수 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
5 3
5 4 3 2 1
1 3
2 4
5 5예제 출력 1
12
9
1문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(reader.readLine());
int N=Integer.parseInt(st.nextToken());
int M=Integer.parseInt(st.nextToken());
int[] arr=new int[N];
int sum=0;
st=new StringTokenizer(reader.readLine());
for(int i=0;i<N;i++) {
sum+=Integer.parseInt(st.nextToken());
arr[i]=sum;
}
for(int m=0;m<M;m++) {
st=new StringTokenizer(reader.readLine());
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
if(a-2<0)
System.out.println(arr[b-1]);
else if(b-1>=N)
System.out.println(arr[N-1]-arr[a-2]);
else
System.out.println(arr[b-1]-arr[a-2]);
}
}
}처음에 간단하다고 생각해서 for문을 이용해서 하나씩 값을 다 더해가는 방식으로 풀었는데 시간초과가 발생했다.
제한사항을 보면 N과 M이 100,000까지 가능한데 for문을 중첩해서 사용하게되면 최대 100,000*100,000 만큼의 시간이 걸릴 수 있기 때문에 시간초과가 발생할 수 밖에 없었다.
시간초과가 발생하지 않게 하려면 배열에 들어오는 값들을 누적해서 적어주고 i번째부터 j번째 구간의 값을 구하기 위해서는
j번째에 들어있는 누적 값-(i-1)번째에 들어있는 누적 값
을 해주면 된다.
이때 배열의 인덱스를 벗어나는 경우가 있는데 i-1번째가 0보다 작아지게 되면 따로 빼는 값 없이 누적 합을 구하면 된다.
반대로 배열의 길이를 넘어가게되면 배열의 끝까지 누적 합을 구하면 된다.
시간초과가 나는 이유를 찾지 못해 헤매다가 같이 문제를 풀던 사람들의 힌트를 받고 풀 수 있었다.
자바에 익숙해지는데에 어려움도 있었지만 다양한 방식의 알고리즘을 이용해야겠다고 생각하게된 문제였다.
