[백준] 11659 - 자바

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

 

구간합은 합배열을 이용해야 하는 문제다.

배열 A = {1,2,3,4,5} 이렇게 있을 때 합배열을 구해놓아야한다.

합배열은 배열 A에 대해서 각 인덱스까지의 합을 아래처럼 더해놓은 값으로 구성된 배열이라 생각하면 된다.

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합

따라서 합배열은 = {1,3,6,10,15} 이렇게된다.

이렇게 구해놓으면 배열 A에서 인덱스1부터 인덱스3까지의 합을 물어보았을 때(즉 2~4까지의 합을 구하라 할 때) 빠르게 처리할 수 있다.

 

아래처럼 단순히 구해도 되겠으나 이러면 시간복잡도가 O(N)이 된다.

int sum = 0;

for(int i=1; i<4; i++){
    sum += arr[i]
}

합배열 S를 구해 아래처럼 한번에 해결할 수도 있다. 이럴경우 시간복잡도 O(1)이다.

int sum =S[3]-S[0]

 

참고로, 합배열을 만드는 방법은 간단하다.

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

---

public class Main {
    public static void main(String[] args) throws IOException {
    /*
    1.n과 m을 받는다
    2.둘째줄에 들어오는 n개의 수를 배열로 받는다.
    3.이 배열을 수의 개수만큼 for반복 돌리면서 합배열을 만든다.
    3.for(반복횟수 m){
    StringTokenizer로 구간을 나타내는 i와 j를 받는다.
    합배열(j)-합배열(i) = 원래배열의 i부터 j까지 합구간
    }
     */

        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());
        StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st2.nextToken());
        }

        int[] sumArr = new int[n];
        sumArr[0]=arr[0];
        for(int i=1; i<n; i++){
            sumArr[i] = sumArr[i-1] +arr[i];
        }

        StringBuilder sb = new StringBuilder();

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

            if(start==1){
              int answer = sumArr[end-1];
                sb.append(answer).append('\n');
            } else{
                int answer = sumArr[end-1] -sumArr[start-2];
                sb.append(answer).append('\n');
            }

        }
        System.out.println(sb);

    }
}

---

반년 전, 알고리즘을 한참 열심히 풀 때의 기록이다.

어차피 계산에는 합배열만 있으면 되니 처음부터 배열을 받지않고 곧바로 합배열을 만들었다.

여기 코드가 더 깔끔하고 나아보인다.

public class Main {
    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()); // 수의 개수 n
        int m = Integer.parseInt(st.nextToken()); // 합을 구해야하는 횟수 m
        int[] arr = new int[n];

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int sum=0;
        for(int i=0; i<n; i++){
             sum+=Integer.parseInt(st2.nextToken());
             arr[i]=sum;
        }

        StringBuilder sb = new StringBuilder();
        for(int x=0; x<m; x++){
            StringTokenizer st3 = new StringTokenizer(br.readLine());
            int i= Integer.parseInt(st3.nextToken())-1;
            int j= Integer.parseInt(st3.nextToken())-1;
            
                if(i==0){
                    sb.append(arr[j]).append("\n");
                } else{
                    sb.append(arr[j]-arr[i-1]).append("\n");
                }
            }
        
        System.out.println(sb);
    }
}