[Java] 백준알고리즘 #11659 구간 합 구하기 4

백준알고리즘 #11659 구간 합 구하기 4

 

주어진 수들의 구간합을 구하는 문제.

단순히 생각하면 다음과 같은 풀이를 구할 수 있다.

// 해설참조 : sehyeok.tistory.com 

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();

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

    }
}

 

주어진 수들을 num배열에 넣고, 시작값과 종료값을 반복문을 통해서 sum변수에 차례대로 더해주는 것.

다만 이렇게 풀이하게 되면 시간 초과 에러가 나온다.

 

때문에 좀 더 영리하게 문제를 해결해보자.

 

1 2 3 4 5의 배열이 있다고 할 때,

시작값이 1, 종료값이 3이라면

1+2+3 = 6이 되고,

시작값이 3, 종료값이 5라면

3+4+5 = 12가 된다.

 

우리는 이 배열을 정리한다거나 할 필요가 없으므로, 애초에 배열에 누적합 값을 넣어주면 된다.

입력한 수가 1 2 3 4 5일 경우

배열에는 1 3 6 10 15가 들어간다고 보면 된다.

이 때 시작값이 1 종료값이 3이라면

종료값 6 (3번째) - 시작값 0 (1-1번째)  = 6 (시작값이1일 경우는 처음부터 세는 경우이므로 - 0  취급)

시작값이 3 종료값이 5라면

종료값인 15 (5번째) - 시작값 3 (3 - 1 번째)  = 12

와 같이 구할 수 있다.

 

이제 코드를 작성해보면

int[] num = new int[n + 1];
num[0] = 0;                             // 배열의 첫번째(0번째)는 0
for (int i = 1; i <= n; i++) {
    num[i] = num[i - 1] + sc.nextInt(); // 누적합
}

 

배열의 0번째 수는 0으로 초기화해 준 후, n번째 배열에 n-1번째까지의 누적합을 저장해준다.

 

for (int i = 0; i < m; i++) {
    int start = sc.nextInt();           // 시작값
    int end = sc.nextInt();             // 종료값

    System.out.println(num[end] - num[start - 1]); // 종료값 - (시작값 - 1)
}

 

이후 반복문을 통해 구간합을 구해주면 완성.

 

전체 코드는 다음과 같다.

// 해설참조 : sehyeok.tistory.com 

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] num = new int[n + 1];
        num[0] = 0;                             // 배열의 첫번째(0번째)는 0
        for (int i = 1; i <= n; i++) {
            num[i] = num[i - 1] + sc.nextInt(); // 누적합
        }
        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();           // 시작값
            int end = sc.nextInt();             // 종료값

            System.out.println(num[end] - num[start - 1]); // 종료값 - (시작값 - 1)
        }

        sc.close();
    }
}