[백준온라인] 11441번 합 구하기

문제 : https://www.acmicpc.net/problem/11441

11441번: 합 구하기

문제 요약 : 부분합 계산

입력	출력
1 ≤ A ≤ 100000 -1000 ≤ A[n] ≤ 1000 1 ≤ s, e(구간) ≤ 100000	주어진 구간의 부분합 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_11441.java

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
31107571	cbkpar	11441	맞았습니다!!	55168KB	672ms	Java 11	800B

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

주어진 수열을 1~n까지 부분합을 미리 계산 후

주어진 구간의 시작을 s 끝을 e라고 할 때

e의 부분합에서 s-1의 부분합을 빼준다.

 

예제 ) 

5

10 20 30 40 50

5

1 3

2 4

3 5

1 5

4 4