[JAVA] 백준 11659: 구간 합 구하기 4

문제

실버 3
https://www.acmicpc.net/problem/11659

풀이

import java.util.Scanner;

public class S3_11659 {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int N = in.nextInt();
    int M = in.nextInt();

    int[] input = new int[N];
    int[] sum = new int[N];
    int[] result = new int[M];

    for (int i = 0; i < N; i++) {
      input[i] = in.nextInt();

      if (i == 0) {
        sum[i] = input[i];
      } else {
        sum[i] = sum[i-1] + input[i];
      }
    }

    for (int x = 0; x < M; x++) {
      int i = in.nextInt() - 1;
      int j = in.nextInt() - 1;

      if (i == 0) {
        result[x] = sum[j];
      } else {
        result[x] = sum[j] - sum[i - 1];
      }
    }

    for (int x = 0; x < M ; x++) {
      System.out.println(result[x]);
    }
  }
}

---

[Do it! 알고리즘 코딩테스트 자바편]

과정

1. 문제 분석 & 풀어보기
1. N개의 수를 입력받음과 동시에 합 배열 생성

S[i] = S[i-1] + A[i]

2. 구간 i, j가 주어지면 구간 합을 구하는 공식으로 정답 출력

S[j] = S[i-1]

2. 슈도코드

3. 코드

	BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

    int suNo = Integer.parseInt(stringTokenizer.nextToken());   // 데이터 개수, 5
    int quizNo = Integer.parseInt(stringTokenizer.nextToken());   // 질의 개수, 3

    long[] S = new long[suNo + 1];   // 1 더해서 6개의 원소를 가진 배열 생성

    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
    for (int i = 1; i <= suNo; i++) {      // 1부터 시작해서
      S[i] = S[i - 1] + Integer.parseInt(stringTokenizer.nextToken());   // 바로 받으면서 합 배열 생성
    }
    
    for (int q = 0; q < quizNo; q++) {
      stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int i = Integer.parseInt(stringTokenizer.nextToken());
      int j = Integer.parseInt(stringTokenizer.nextToken());
      System.out.println(S[j] - S[i - 1]);   // 구간 합 구하기
    }

---

여담

생각보다 오래 걸렸다...