[백준 11659] 구간 합 구하기 4 (S3)

📍 문제 

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

 

📍 문제 풀이

 

두가지 방법으로 풀어봤다.

• 이중 for문을 이용한 풀이 `O(NM)` > 시간초과를 당연히 예상했다 
• 인덱스별 누적합을 미리 구해서 배열로 만들어 놓는 방법 `O(N+M)`

첫번째 방식은 단순히 i부터 j까지의 합을 구하는 방식이다. 결과적으로 시간초과가 발생했다. 

두번째 방식은 누적합을 구하는 방식인데, 미리 인덱스별로 누적합 값을 배열로 저장해둔다.

그 후에는 해당 값들끼리 연산을 해주면 되는데

예를 들어 `i = 2, j = 4`라면 `(1,4) - (1,2)`를 구한다. 

즉, `prefix[4] - prefix[2]` 를 구하면 된다.

 

 

 

📍 전체 코드

1. 단순합 계산 > 시간초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_11549 {
    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());
       int[] nums = new int[n];
       st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          nums[i] = Integer.parseInt(st.nextToken());
       }

       for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int start = Integer.parseInt(st.nextToken());
          int end = Integer.parseInt(st.nextToken());

          int sum = 0;
          for (int j = start-1; j < end; j++) {
             sum += nums[j];
          }
          System.out.println(sum);
       }
    }
}

 

 

2. 누적합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_11549 {
    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());

       int[] nums = new int[n + 1];
       int[] prefix = new int[n + 1];
       st = new StringTokenizer(br.readLine());
       for (int i = 1; i <= n; i++) {
          nums[i] = Integer.parseInt(st.nextToken());
          prefix[i] = prefix[i - 1] + nums[i];

       }

       for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int start = Integer.parseInt(st.nextToken());
          int end = Integer.parseInt(st.nextToken());
          System.out.println(prefix[end] - prefix[start - 1]);
       }

    }
}