003. 구간 합 구하기1 (백준11659)

문제 분석

수의 개수와 합을 구해야하는 횟수는 최대 100,000
질의 1개당 최대 100,000번의 연산*최대 질의 수 100,000 = 10,000,000,000
⭐최악의 경우 1억회 이상의 연산수행, 1초 이상의 수행 시간이 필요함
따라서, 합배열 공식 사용

손으로 풀기

합배열 공식: S[i] = S[i-1] + A[i]
ex.

인덱스	1	2	3	4	5
배열 A	5	4	3	2	1
합 배열 S	5	9	12	14	15

구간 합: S[j] - S[i-1]

슈도코드 작성

 N(숫자개수), M(질의개수)
for(숫자개수만큼 반복) {
	합 배열 생성하기(S[i] = S[i-1] + A[i])
}
for(질의 개수만큼 반복) {
	질의 범위 받기(i~j)
    구간 합 출력(S[j] - S[i-1])
}

정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p11659_구간합구하기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());   // 숫자개수
        int M = Integer.parseInt(st.nextToken());   // 질의개수

        // 합배열S는 덧셈곱셈이 많으면 int 범위 넘을 가능성있으므로 long으로 선언
        long[] S = new long[N + 1];
        st = new StringTokenizer(br.readLine());    // 한줄 받기
        for(int i=1; i<=N; i++) {   // 0번째 인덱스 무시
            S[i] = S[i-1] + Integer.parseInt(st.nextToken());   // 합배열
        }
        for(int k=0; k<M; k++) {
            st = new StringTokenizer(br.readLine());    // 한줄 받기
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            System.out.println(S[j] - S[i-1]);	// 구간 합
        }
    }
}