[백준] 11659번 구간 합 구하기 4
문제 및 입출력
문제 접근
누적합 배열을 이용하여 해결하였다.
N개의 수를 입력 받을 때, 전까지의 수를 더하여 누적 합 배열을 구한다.
arr[i] = arr[i - 1] + integer;
이후, i부터 j까지의 합을 누적합에서 j까지의 누적 합에서 i-1까지의 누적합을 빼는 방식으로 구한다.
arr[j] - arr[i - 1]
구현 코드
import java.io.*;
import java.util.*;
public class Main {
public static int[] arr;
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());
arr = new int[N+1];
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++) {
arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
}
for(int k = 0; k < M; k++) {
st = new StringTokenizer(br.readLine());
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
System.out.println(arr[j] - arr[i-1]);
}
}
}
Author And Source
이 문제에 관하여([백준] 11659번 구간 합 구하기 4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choiish98/백준-11659번-구간-합-구하기-4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)