백준 : 19951 - 태상이의 훈련소 생활

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

문제는 간단했는데,,

이것도 시간걸리는걸 생각했어야 했다!

문제읽으면서 동생이 생각났다... 가스조절기는 잃어버리지 말자

---

처음에는 간단하게 생각했다.

Index [a-1] ~ [b-1] 까지 k를 누적시켜준다.

void solution1(){
    // 시간초과
    int n, m;
    vector<int> grounds;
    cin >> n;
    cin >> m;

    for(int i = 0; i<n; i++){
        int temp;
        cin >> temp;
        grounds.push_back(temp);
    }

    for(int i = 0; i<m; i++){
        int a, b, k;
        cin >> a;
        cin >> b;
        cin >> k;
        for(int j = a-1; j<b; j++){
            grounds[j] += k;
        }
    }

    for(int i = 0; i<n; i++){
        cout << grounds[i] <<" ";
    }
}

근데!! 시간초과가 나왔다.

저기 반복문이 2번 중첩되는 부분이 문제였다.

일단 m만큼 반복하고, 그 안에 a-1 ~ b반복하는게 최대 n까지 가능하므로

시간복잡도는 mn, 이 때 문제에서 m이랑 n이랑 같은 제한범위를 가지므로 n^2 시간복잡도랑 비슷해진다!

 

생각해야 할건 누적합이다!

이런식으로 생각해보면

배열에서 k를 저장하는건 보라색 지점 (a-1가 인덱스인곳) 뿐이다! (나머지는 0으로 내비두기)

그 다음부터는 누적을 해주면 된다!

만약 범위가 끝나면? index가 b인 부분에 -k를 저장해주면, 똑같이 누적합연산을 해주기만 해도 알아서 처리된다.

 

int main(){

    int n, m;
    vector<int> grounds;
    cin >> n;
    cin >> m;

    for(int i = 0; i<n; i++){
        int temp;
        cin >> temp;
        grounds.push_back(temp);
    }
    
    vector<int> changes(n, 0);

    for(int i = 0; i<m; i++){
        int a, b, k;
        cin >> a;
        cin >> b;
        cin >> k;
        changes[a-1] += k;
        if(b<n){
            changes[b] += -k;
        }
        
    }

    int sum = 0;
    for(int i = 0; i<n; i++){
        sum+=changes[i];
        cout << (grounds[i] + sum) <<" ";

    }

    return 0;
}

 

---

완전 생각을 못했다.......

그래 이렇게 문제가 쉬울리가 없지..ㅋㅋㅋㅋㅋ