11659: 구간 합 구하기 4(java)

문제

---

풀이

 

m부터 n까지의 부분 합은 0부터 m까지의 부분 합에서 0부터 (n-1)까지의 부분 합을 뺀 값임을 이용한다.

 

입력된 수들을 저장할 arr 배열과 0부터 n까지의 배열을 저장할 sum 배열을 선언했을 때, i부터 j까지의 부분 합은 (sum[j]-sum[i-1])이다.

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{
		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());
		
		st=new StringTokenizer(br.readLine());
		
		int[] arr=new int[N];
		int[] sum=new int[N+1];
		
		for(int i=0; i<N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
			sum[i+1]=sum[i]+arr[i];
		}
		
		StringBuilder sb=new StringBuilder();
		
		for(int i=0; i<M; i++) {
			st=new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			
			sb.append(sum[y]-sum[x-1]).append("\n");
		}
		
		System.out.println(sb);
	}
}

 

++

이중 for문을 사용해 결과 배열에 += arr[i] 하는 방식으로 풀이하면 \(O(N^2)\)의 시간복잡도를 가지게 되므로 제한 시간 조건에 부합하지 않는다.

//오류 코드
for(int i=0; i<M; i++){	//O(N^2)
	st=new StringTokenizer(br.readLine());
	int left=Integer.parseInt(st.nextToken());
    int right=Integer.parseInt(st.nextToken());
    
    sum = 0
    
    for(int j=left-1; j<right; j++){
    	sum+=arr[j];
    }
}