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

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

11659번: 구간 합 구하기 4

 

- 수 N개가 주어졌을 떄, i번째 수부터 j번째 수까지 합을 구하는 프로그램

 

문제 풀이 

 

구간 합(Prefix Sum) 알고리즘 

 

[알고리즘] - 구간 합 (Prefix sum) (tistory.com)

[알고리즘] - 구간 합 (Prefix sum)

- 수열에서 특정 구간의 합을 구할 때  시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

 

부분 합(Partial sum)

- 처음부터 k번 인덱스까지의 합 

 

구간 합(Prefix sum)

- i번부터 j번 인덱스까지의 합 

 

1) 합 배열 만들기 

 

 

 

- sum[i[는 기존 배열 num의 0번 인덱스부터 i번 인덱스까지의 합 (누적 합과 같음)

- sum을 선언할 때 0으로 초기화하여 선언한 후, num에 i번째 값이 들어올 때마다 sum[i]에 num을 더해주면 됨

 

sum[i] = sum[i-1]+num[i];

 

- num은 굳이 배열로 선언하여 입력받을 필요 없이, 반복문 안에서 해당 횟수만큼 입력받은 후 sum에 더해주기만 하면 됨

 

 

2) 합 배열을 이용하여 구간 합 구하기 

 

 

//i에서 j까지의 구간 합
sum[j] - sum[i-1];

 

- i번 인덱스부터 j번 인덱스까지의 구간 합은, sum[j]에서 sum[i-1]을 빼주면 됨

- i번 인덱스 위치의 값도 포함해야 하므로 sum[i]가 아닌 sum[i-1]을 빼주어야 함

 

 

정답

 

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

public class Main {
    static int n;
    static int m;
   
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st;
        st= new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        int sum [] = new int[n+1]; //합 배열
        
        st= new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++)
        {
            int num = Integer.parseInt(st.nextToken());
            
            //새 입력이 들어올 때마다 sum[i-1]에 더해서 sum[i]에 대입
            sum[i] = sum[i-1]+num;
        }
        
        for(int i=0; i<m; i++)
        {
           st = new StringTokenizer(br.readLine());
           int a = Integer.parseInt(st.nextToken());
           int b = Integer.parseInt(st.nextToken());
           
           int result = sum[b] - sum[a-1];
       
           bw.write(result+"");
           bw.newLine();
            
        }
        
        bw.flush();
        bw.close();
    }
}