11659번: 구간 합 구하기 4

 

- 문제 사이트: https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

정석적으로 풀면 문제 그대로 시작 번호부터 끝 번호까지 더해서 출력해주면 된다.

하지만, 이 경우 시작과 끝의 간격이 클 수록 계산하는데 시간이 오래 걸린다.

따라서, 로직 상으로는 맞지만 시간 초과 결과를 받게 된다.

 

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M, i, j;
    cin >> N >> M;
    int num[N];
    for (int& n : num)
        cin >> n;
    
    while (M > 0)
    {
        long long int sum = 0;
        cin >> i >> j;
        for (int idx = i - 1; idx < j; idx++)
        {
            sum += num[idx];
        }
        cout << sum << "\n";
        M--;
    }
    return 0;
}

- 시간 초과

 

i번부터 j번까지의 합은 (1번 ~ j번까지의 합) - (1번 ~ (i-1)번까지의 합) 과 동일하다.

 

3번까지의 합 = 1번 + 2번 + 3번

7번까지의 합 = 1번 + 2번 + 3번 + 4번 + 5번 + 6번 + 7번

3번부터 7번까지의 합 = 3번 + 4번 + 5번 + 6번 + 7번 = 7번까지의 합 - 2번까지의 합

 

따라서, N개의 숫자를 입력받을 때, 현재 숫자까지의 누적합을 저장해주고

범위가 주어졌을 때 각 누적값의 차이를 계산하여 출력해주도록 한다.

 

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, i, j, num;
    cin >> N >> M;
    
    long long int sum[N + 1];
    sum[0] = 0;
    for (int n = 1; n <= N; n++)
    {
        cin >> num;
        sum[n] = sum[n - 1] + num;
    }
    
    for (int m = 0; m < M; m++)
    {
        cin >> i >> j;
        cout << sum[j] - sum[i - 1] << "\n";
    }
    return 0;
}

- 메모리: 2680 KB

- 시간: 40 ms

- 코드 길이: 460 B