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

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

11659번: 구간 합 구하기 4

 

array[]에서 i 부터 j 까지 의 수들을 더하면 된다.

아무생각 없이 그냥 이중for문 썼는데

이렇게 시간 초과가 뜬다.

시간 복잡도를 줄이려면 당연히 이중for문을 없애야 되겠지

 

구간 합을 구하는 공식으로 풀면 된다.

사실 문제 제목 자체가 '구간 합 구하기'니까 당연한 소리다.

 

예시로 주어진 배열 A는 [ 5, 4, 3, 2, 1 ]이다.

합 배열을 만들어주면

배열 S[ 5, 9, 12, 14, 15 ]가 만들어진다.

 

합 배열을 만드는 공식은

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

이다.

 

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

이해가 되는가?

 

아 그러면 배열A와 합 배열S를 만들어서 구하면 되는 건가?

땡이다.

아니다.

굳이 불필요하게 배열을 하나 더 만들 필요 없다.

쓸 데 없이 for문 하나 추가하여 계산 시간을 늘릴 필요는 없다.

 

그러면 이제 i에서 j까지의 합을 구하는 공식을 알아보자

S[ j ] - S [ i - 1]이다.

2를 구하고 싶다면 5(전체)에서 3(나머지)을 빼면 된다.

해당 공식도 똑같다.

전체 합 ( j )에서 시작할 부분 이전 ( i )을 빼주면 된다.

 

이게 끝이다.

하지만 굳이 배열A를 만들어 줄 필

 

이전 코드

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        int arrayCount = Integer.parseInt(st.nextToken());
        int repeatCount = Integer.parseInt(st.nextToken());

        Integer[] array = new Integer[arrayCount];
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < arrayCount; i++) array[i] = Integer.parseInt(st.nextToken());

        int start;
        int end;
        int sum;
        for (int i = 0; i < repeatCount; i++) {
            st = new StringTokenizer(bf.readLine());
            sum = 0;
            start = Integer.parseInt(st.nextToken()) - 1;
            end = Integer.parseInt(st.nextToken()) - 1;
            for (int j = start; j < end + 1; j++) sum += array[j];
            bw.write(String.valueOf(sum));
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }

 

문제를 읽어보니 N의 범위로 보아 int로는 안 되어 long으로 바꿔주었다.

수정 후 코드

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

public class Main {
    private static long[] array;
    private static long[] subArray;
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        int arrayCount = Integer.parseInt(st.nextToken());
        int repeatCount = Integer.parseInt(st.nextToken());

        array = new long[arrayCount];
        subArray = new long[arrayCount + 1];

        st = new StringTokenizer(bf.readLine());
        for (int i = 1; i <= arrayCount; i++) buildSubArray(i, Integer.parseInt(st.nextToken()));

        int startIndex;
        int endIndex;
        for (int i = 0; i < repeatCount; i++) {
            st = new StringTokenizer(bf.readLine());
            startIndex = Integer.parseInt(st.nextToken());
            endIndex = Integer.parseInt(st.nextToken());
            findSubBySection(startIndex, endIndex);
        }
        bw.flush();
        bw.close();
    }

    private static void buildSubArray(int i, Integer element) {
        subArray[i] = subArray[i - 1] + element;
    }

    private static void findSubBySection(int i, int j) throws IOException {
        long sub = subArray[j] - subArray[i - 1];
        bw.write(String.valueOf(sub));
        bw.newLine();
    }
}