백준 11441 합 구하기(Java)

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

11441번: 합 구하기

---

 

해석 및 팁

 

---

 

이 문제를 풀 때 이중반복문을 사용하면 시간초과가 발생하므로 누적합을 이용해서 풀어야힙니다. a->b의 합으로 구하려면 0->b의 합에서 0->a-1의 합을 빼주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int n = sc.nextInt();
    int[] arr = new int[n + 1];
    for(int i = 1; i <= n; i++) arr[i] = arr[i - 1] + sc.nextInt();
    int m = sc.nextInt();

    for(int i = 0; i < m; i++) {
      int sum = 0;
      int a = sc.nextInt();
      int b = sc.nextInt();
      sb.append(arr[b] - arr[a - 1]).append("\n");
    }

    System.out.println(sb);
  }
}