[백준OJ] 2900번 프로그램

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

2900번: 프로그램

---

 

-풀이-

문제대로 해주면되는데 주의해주어야할점이 있다.

1. 받는 x값 마다 something함수를 실행시켜주면 시간초과가 날것이다.

2. 받는 L,R 값 마다 L~R까지의 합을 FOR문을 이용해 구해주면, 시간초과가 날것이다.

 

1번 문제점을 해결해주기 위해, 입력받는 x값을 map을 이용하여 갯수를 세어준다. 그런 뒤, 저장된 x값과 cnt를 이용해주어서 something함수를 실행시켜주는데, jump인자와 cnt인자를 사용하여 a[i]=a[i]+cnt를 실행시켜준다.

ex) jump=1 , cnt=2라고 하자.

0~N까지 1간격으로 1을 더해주는 함수를 2번 실행하는 것과,

0~N까지 1간격으로 2를 더해주는 함수를 1번 실행하는 것과는 시간에 차이가 생긴다. 따라서 x값이 몇번씩 나왔는지 체크해주고, something함수를 실행시켜줄 때 x값이 나온 횟수만큼 더해주면 된다.

 

2번 문제점을 해결해주기 위해, 누적합을 이용해준다.  누적합을 이용해주면 매 쿼리마다 O(R-L) 시간이 걸리는 합 구하기를 , 초반 O(N)을 투자하여, 매 쿼리마다 O(1)로 해결해 줄 수 있기떄문이다.

 

-코드-

#include <algorithm>
#include<iostream>
#include<map>

using namespace std;

int N,K,Q;
long long a[1000001]={0};
long long s[1000001]={0};
map<int,int> X;
void something(int jump,int cnt){
    int i=0;
    while(i<N){
        a[i]=a[i]+cnt;
        i=i+jump;
    }
}

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    cin>>N>>K;
    for(int i=0;i<K;i++){
        int x;
        cin>>x;
        X[x]++;
    }
    
    for(auto x:X){
        int jump=x.first;
        int cnt=x.second;
        something(jump,cnt);
    }
    
    
    s[0]=a[0];
    
    for(int i=1;i<N;i++){
        s[i]=s[i-1]+a[i];
    }
    
    cin>>Q;
    for(int i=0;i<Q;i++){
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<"\n";
    }
}