본문 바로가기
알고리즘

[백준 11659] 알고리즘 62일차 : 구간 합 구하기4

by SiO2whocode 2021. 1. 11.
반응형

www.acmicpc.net/problem/11659

 

11659번: 구간 합 구하기 4

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j

www.acmicpc.net

C++ 누적합

문제 처음 보면 엥 이게 왜 실버3이지 싶은데 풀고나면 아ㅇㅇ

 

그냥 수배열 주고 일정 구간 수의 합 구하는건데 시간복잡도 때문에 그냥 합하는 식으로 구하면 시간초과나고

누적합.. 아 이 문제 분류가 누적합이구나..

입력받을때 누적합을 같이 구해서 구간 합 구할때는

sum[end] - sum[start] (단, start != 1) 로 구해야 함

 

근데도 시간초과 나서 sync랑 cin tie null 해줬어요.

사실 오늘 다익스트라 풀고있었는데 인접행렬로 풀었더니 메모리 초과나서 내일 다시 짜려구요..

 

소스코드

 

#include <iostream>
using namespace std;
int sum[100001];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, I, s,e;
    cin >> N >> I;
    int num[N+1];
    for(int i = 1 ; i <= N ; i++){
        cin >> num[i];
        if(i == 1){
            sum[i] = num[i];
        }else{
            sum[i] = sum[i-1]+num[i];
        }
    }
    for(int i = 0 ; i < I ; i++){
        cin >> s >> e;
        if(s>1){
            cout << sum[e] - sum[s-1] << "\n";
        }else{
            cout << sum[e] << "\n";
        }
    }
    
    return 0;
}
반응형

댓글0