[자바, C++] 백준 11659 - 구간 합 구하기 4 (java cpp)

 문제 : boj11659

---

 

필요 알고리즘 개념

•  누적합 알고리즘 (prefix sum)
  • 누적합 알고리즘을 사용해 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  누적합 알고리즘의 가장 기본이 되는 문제이다. 설명은 적어둔게 있으므로, 누적합 알고리즘을 모른다면 이 글을 읽어보고 풀면 바로 풀 수 있다.

 

 

---

 

코드 (Java) : github

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 M = 0;
	static int[] arr = null;
	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 = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		arr[0] = Integer.parseInt(st.nextToken());
		for (int i = 1; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken()) + arr[i-1];
		}
		while (K-->0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			bw.write(arr[b-1] - (a-1==0?0:arr[a-2]) + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

 

 

코드 (C++) : github

#include <iostream>
#include <vector>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> arr;
    int n, m, tmp;
    cin >> n >> m;
    arr.push_back(0);
    while (n--) {
        cin >> tmp;
        tmp += arr.back();
        arr.push_back(tmp);
    }
    int a, b;
    while (m--) {
        cin >> a >> b;
        cout << arr[b]-arr[a-1] << '\n';
    }
}