[JAVA] 구간 합 구하기 (백준 11659번)

유형)  자료구조

제한)  0.5초

문제)  N개가 주어졌을 때 i번째 수에서 j번째 수까지의 합을 구하는 프로그램을 작성하시오.   

 

// ----------- 문제: 03 구간 합 구하기 ----------
// 1번째 줄: 수의 개수N (1 <= N <= 100,000), 합을 구해야하는 갯수의 개수M (1 <= N <= 100,000)
// 2번째 줄: N개의 수
// 3번째 줄: M개의 줄에 합을 구하는 i와 j 구간
 
 
// ----------- 입력 & 결과 ----------
5 3        // 5개의 수, 3번 합을 구할 예정
5 4 3 2 1  // 숫자 나열 <-- arr배열에 저장.
1 3        // 12 (1~3번까지의 구간 합)
2 4        //  9 (2~4번까지의 구간 합)
5 5        //  1 (5~5번까지의 구간 합)
 
 
// ----------- 공식 ----------
/*
    합배열 공식: Sum[i] = Sum[i-1] + arr[i] (arr배열을 코드상에서는 token으로 대체함.)
    Sum[0] =  0
    Sum[1] =  0 + 5 = 5
    Sum[2] =  5 + 4 = 9
    Sum[3] =  9 + 3 = 12
    Sum[4] = 12 + 2 = 14
    Sum[5] = 14 + 1 = 15    
 
    구간 합 공식: Sum[j] - Sum[i-1]
    질의(1,3) = 12 -  0 = 12
    질의(2,4) = 14 -  5 = 9
    질의(5,5) = 15 - 14 = 1
*/ 
 
// ----------- 코드 ----------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Test {
    public static void main(String[] args) throws IOException {
 
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); //scanner보다 처리속도가 빠름.
        StringTokenizer st = new StringTokenizer(bf.readLine()); // 여러개의 값을 String타입으로 저장.
        int suNo = Integer.parseInt(st.nextToken());   // 숫자 개수, int로 형변환 후 저장
        int quizNo = Integer.parseInt(st.nextToken()); // 질의 개수, int로 형변환 후 저장
        long[] Sum = new long[suNo + 1];     // 범위오류로 인한 계산 에러를 막고자, int 대신 long을 선언함. 배열이 1부터 시작하도록 +1 해줌.
 
        st = new StringTokenizer(bf.readLine());
        // 합 배열 생성
        for(int i = 1; i <= suNo; i++){
            Sum[i] = Sum[i-1] + Integer.parseInt(st.nextToken()); // suNo개수 만큼 토큰값 하나씩 읽어와 계산
        }
 
        // 질의 개수만큼 반복하여 구간 합 출력
        for(int q = 0; q < quizNo; q++){
            st = new StringTokenizer(bf.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            System.out.println(Sum[j]-Sum[i-1]);
        }
    }
}

 

< console result >