[Java] 백준 11659 구간 합 구하기 4 (자료구조1,구간합/합배열)

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

 

 

[문제분석] 

특정 인덱스 구간의 배열 데이터들을 전부 더해야 하므로

합배열을 이용한 구간 합 알고리즘을 사용해야 한다.

 

---

[진행순서]
1. 데이터개수, 문제개수 입력받기
2. 입력받았던 데이터 개수만큼 합배열 선언
3. 입력받았던 문제 개수만큼 구간합 출력

 

---

 

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

public class Main {

    public static void main(String[] args) throws IOException {

        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);

        // 데이터개수, 문제개수 입력
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
        int 데이터개수 = Integer.parseInt(stringTokenizer.nextToken());
        int 문제개수 = Integer.parseInt(stringTokenizer.nextToken());

        // 합배열
        long[] S = new long[데이터개수 + 1];

        // 합배열 공식
        stringTokenizer = new StringTokenizer(br.readLine());
        for(int i = 1; i<= 데이터개수; i++){
            S[i] = S[i-1] + Integer.parseInt(stringTokenizer.nextToken());
        }

        // 구간합 공식
        for (int q = 0; q<문제개수; q++){
            stringTokenizer = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(stringTokenizer.nextToken());
            int j = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(S[j] - S[i-1]);
        }

    }
}

 

---

 

+ 문제풀이 예시

첫번째: 5 1

두번째: 5 4 3 2 1

세번째: 1 3

입력