[JAVA/백준] 11659번 : 구간 합 구하기4

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

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

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

 

 

*제한

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

 

<examples>

-입력

5 3
5 4 3 2 1
1 3
2 4
5 5

 

-출력

12
9
1

 

 

 

 

 

[풀이]

package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
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 suNo = Integer.parseInt(st.nextToken());//tokenizer로 쪼갠 첫 원소 할당
        int quizNo = Integer.parseInt(st.nextToken());
        long[] S = new long[suNo+1];
        st = new StringTokenizer(br.readLine());//reader로 다시 읽어
        for(int i =1;i<=suNo;i++){
            S[i] = S[i-1] + Integer.parseInt(st.nextToken());//합배열
        }
        for(int q=0;q<quizNo;q++){
            st = new StringTokenizer(br.readLine());//reader로 다시 읽어
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());//그때마다 입력 받아서
            System.out.println(S[j] - S[i-1]);
        }
    }
}

 

 

---

 

 

구간합을 이용한 문제이다.

배열을 사용자로부터 입력받고 합 배열S를 만들어

수식으로 값을 print해준다.

 

1차원 합 배열의 수식은 다음과 같다.

S[i] = S[j] - S[i-1]