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

 

11441번: 합 구하기

첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는

www.acmicpc.net

코드설명

누적합 문제입니다.

 

누적합을 그대로 구현하면됩니다.

2에서 5까지의 구간합을 구하려고한다면,

prefixSum[5] - prefixSum[1] 을 구해야 2~5까지의 합이 나옵니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static int[] arr;
	public static int[] prefixSum;
	public static long answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
 
    	N = Integer.parseInt(st.nextToken());
    		
    	int sumValue = 0;
    	prefixSum = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		sumValue += Integer.parseInt(st.nextToken());
    		prefixSum[i+1] = sumValue;
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		
    		System.out.println(prefixSum[b] - prefixSum[a-1]);
    	}
    
//    	System.out.println(answer);
    }
    
    
}

 

다르게 풀어본 누적합 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
    private static int N, T, K, M;
    private static int answer = 0;
    private static int[] arr;
    private static int[] prefixSum;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		prefixSum = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			prefixSum[i] = i == 0 ? arr[i] : prefixSum[i-1] + arr[i];
		}
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int lo = Integer.parseInt(st.nextToken());
			int hi = Integer.parseInt(st.nextToken());
			
			int loSum = lo - 1 == 0 ? 0 : prefixSum[(lo - 1) - 1];
			int hiSum = prefixSum[hi - 1];
			System.out.println(hiSum - loSum);
		}
	}
    
}

'알고리즘 > Prefix_Sum' 카테고리의 다른 글

[백준] 16507 어두운 건 무서워 - 2차원 누적합(2차원 Prefix Sum) JAVA  (0) 2023.08.13
[백준] 11441 인간-컴퓨터 상호작용 - 누적합(Prefix Sum) + DP + 알파벳(문자열) JAVA  (0) 2023.08.13
[백준] 11659 구간 합 구하기 4 - 누적합(Prefix Sum) JAVA  (0) 2023.08.13
[백준] 10986 나머지 합- 누적합(Prefix Sum) + 수학(나머지) JAVA  (0) 2023.08.13
[백준] 1806 부분합 - 누적합(Prefix Sum) + 투포인터(Two Poitner) JAVA  (0) 2023.08.11

+ Recent posts

티스토리툴바