[Baekjoon] 11659번: 구간 합 구하기 4 - Java

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

11659번: 구간 합 구하기 4

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램이다.

풀이 방법 1: 반복문 - 시간 초과

처음 문제를 보고 단순히 i부터 j까지 더하는 식으로 구하도록 프로그램을 작성했으나 시간 초과가 발생했다.

for (int line = 0; line < M; line++) {
    int[] range = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                        .toArray();
    int sum = 0;
    int start = range[0];
    int end = range[1];
    
    for (; start <= end; start++)
        sum += nums[start];
        
    sb.append(sum).append("\n");
}

풀이 방법 2: 구간 합 구해놓기 - 통과

문제를 해결하기 위해 구간 합을 먼저 구해놓도록 했다.

구간 합만을 구하는 문제이기 때문에 입력받을 때 구간 합을 만들어 놓는다. 그다음 뒤쪽 합에서 앞쪽 합을 빼면 원하는 구간 합이 나온다.

sums = new int[N + 1];
nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int i = 1; i <= N; i++)
    sums[i] = sums[i - 1] + nums[i - 1];

for (int line = 0; line < M; line++) {
    int[] range = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                        .toArray();
    int start = range[0];
    int end = range[1];
    sb.append(sums[end] - sums[start - 1]).append("\n");
}

전체 코드는 다음과 같다.

package baekjoon.math;

import java.io.*;
import java.util.Arrays;

public class BOJ11659 {

    static int N;
    static int M;
    static int[] nums;
    static int[] sums;
    static StringBuffer sb = new StringBuffer();

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] split = br.readLine().split(" ");
            N = Integer.parseInt(split[0]);
            M = Integer.parseInt(split[1]);

            sums = new int[N + 1];
            nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int i = 1; i <= N; i++)
                sums[i] = sums[i - 1] + nums[i - 1];

            for (int line = 0; line < M; line++) {
                int[] range = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                        .toArray();
                int start = range[0];
                int end = range[1];
                sb.append(sums[end] - sums[start - 1]).append("\n");
            }

            System.out.print(sb);
        }
    }
}