(JAVA) [BOJ]백준 11659번, 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

11659, 구간 합 구하기 4

[ 난이도 : 실버 3 ]

이번 문제는 누적합을 사용해서 풀어보겠다.

 

N과 M의 범위가 1 - 100,000 이다. 이번 문제에선 i, j 를 for문을 통해서 구하게 되면 시간 초과가 발생할 수 있기 때문에

누적합을 통해 풀어보겠다.

 

예를 들어 i, j 가 각각 2 와 3으로 주어지고 arr이라는 int 배열에 누적합을 구한다는 가정을 해보겠다.

 arr[2] = 1번 원소 + 2번 원소

 arr[3] = 1번 원소 + 2번 원소 + 3번 원소

로 구성될 것이다.2와 3의 구간을 구하려면 (1번 원소 + 2번 원소 + 3번 원소) 에서 1번 원소만 빼주면 된다.

 

즉 3번 요소까지의 누적합에서 1번 요소까지의 누적합을 제거하면 된다.이를 구하려면 arr[i] - arr[j-1] 이라는 식을 구할 수 있다.

# Process

1. input

static int N, M;
static int[] arr;

static void input() 
{
    N = scan.nextInt();
    M = scan.nextInt();

    arr = new int[N+1];
    // 누적합 구하기
    for(int i=1; i<=N; i++) arr[i] = arr[i-1] + scan.nextInt();
}

 

2. Calculate

: 위에서 설명한대로 값을 도출하면 된다.

static void pro()
{ 
    while(M-- >0)
    {
        int start = scan.nextInt(), end = scan.nextInt();

        sb.append((arr[end]-arr[start-1])+"\n");
    }

    System.out.println(sb);
}

전체 코드

static int N, M;
static int[] arr;

static void input() 
{
    N = scan.nextInt();
    M = scan.nextInt();

    arr = new int[N+1];
    // 누적합 구하기
    for(int i=1; i<=N; i++) arr[i] = arr[i-1] + scan.nextInt();
}

static void pro()
{ 
    while(M-- >0)
    {
        int start = scan.nextInt(), end = scan.nextInt();

        sb.append((arr[end]-arr[start-1])+"\n");
    }

    System.out.println(sb);
}

public static void main(String[] args) 
{
    input();
    pro();
}