N과 M의 범위가 1 - 100,000 이다. 이번 문제에선 i, j 를 for문을 통해서 구하게 되면 시간 초과가 발생할 수 있기 때문에
누적합을 통해 풀어보겠다.
예를 들어 i, j 가 각각 2 와 3으로 주어지고 arr이라는 int 배열에 누적합을 구한다는 가정을 해보겠다.
arr[2] = 1번 원소 + 2번 원소
arr[3] = 1번 원소 + 2번 원소 + 3번 원소
로 구성될 것이다.2와 3의 구간을 구하려면 (1번원소+ 2번원소+ 3번 원소) 에서 1번 원소만 빼주면 된다.
즉 3번 요소까지의 누적합에서 1번 요소까지의 누적합을 제거하면 된다.이를 구하려면 arr[i] - arr[j-1] 이라는 식을 구할 수 있다.
# Process
1. input
static int N, M;
static int[] arr;
static void input()
{
N = scan.nextInt();
M = scan.nextInt();
arr = new int[N+1];
// 누적합 구하기
for(int i=1; i<=N; i++) arr[i] = arr[i-1] + scan.nextInt();
}
2. Calculate
: 위에서 설명한대로 값을 도출하면 된다.
static void pro()
{
while(M-- >0)
{
int start = scan.nextInt(), end = scan.nextInt();
sb.append((arr[end]-arr[start-1])+"\n");
}
System.out.println(sb);
}
전체 코드
static int N, M;
static int[] arr;
static void input()
{
N = scan.nextInt();
M = scan.nextInt();
arr = new int[N+1];
// 누적합 구하기
for(int i=1; i<=N; i++) arr[i] = arr[i-1] + scan.nextInt();
}
static void pro()
{
while(M-- >0)
{
int start = scan.nextInt(), end = scan.nextInt();
sb.append((arr[end]-arr[start-1])+"\n");
}
System.out.println(sb);
}
public static void main(String[] args)
{
input();
pro();
}