백준 17128번: 소가 정보섬에 올라온 이유 (C++)

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

17128번: 소가 정보섬에 올라온 이유

---

Solved By: Implementation

 

Try 1)

실제로 모든 값을 계속 구하다가 O(NQ)로 인해 시간 초과가 났습니다.

 

Try 2)

식을 정리해보다가 다음과 같은 규칙을 발견했습니다.

계산 식을 통해 구한 값이 다음 쿼리에 대한 값과 연관이 있습니다.

 

예를 들어 N의 크기가 5이고, Query에서 3을 요청한다면 3번째 원소만 들어가는 곱셈 값들을 구해보면 다음과 같습니다.

- A1A2A3A4 - A2A3A4A5 - A3A4A5A1 - A5A1A2A3입니다. 이 값을 간단하게 subtractValue라고 하겠습니다.

 

원래 구한 값은

A1A2A3A4 + A2A3A4A5 + A3A4A5A1 + A4A5A1A2 + A5A1A2A3이고,

쿼리를 통해서 구해지는 값은

- A1A2A3A4 - A2A3A4A5 - A3A4A5A1 + A4A5A1A2 - A5A1A2A3입니다.

이전 원래 구한 값에서 2 * subtractValue를 빼주면 우리가 원하는 답을 구할 수 있게 됩니다.

 

즉, 쿼리로 들어온 인덱스에 해당하는 value가 들어가는 곳은 4곳이며 곳마다 곱셈 연산을 4번 하기 때문에 한 쿼리당 O(16) = O(1)로 O(Q)로 줄일 수 있습니다.

 

그리고, 구현을 하는 데에 있어 이번 문제는 index를 넘어가는 오류를 발생하지 않기 위해 모듈러 연산이나 뺄셈 연산을 이용하여 이를 방지해야 합니다.

#include <iostream>
#include <vector>
using namespace std;

int n, q;
vector<int> arr;
vector<int> query;

int main(){
    cin >> n >> q;
    for(int i = 0, v; i < n; i++){
        cin >> v; arr.push_back(v);
    }
    
    for(int i = 0, v; i < q; i++){
        cin >> v; query.push_back(v);
    }
    
    // 기존 sum
    int sum = 0;
    for(int i = 0; i < n; i++){
        int tmp = 1;
        for(int j = i; j < i + 4; j++){
            tmp *= arr[j % n];
        }
        sum += tmp;
    }
    
    for(int Q = 0; Q < q; Q++){
        int qIdx = query[Q] - 1; // -1을 곱할 array's Index
        
        int subtractValue = 0;
        for(int i = qIdx; i > qIdx - 4; i--){
            int tmp = 1;
            int tempI = i >= 0 ? i : n + i; // index over 방지
            for(int j = tempI; j < tempI + 4; j++){
                int tempJ = j % n; // index over 방지
                tmp *= arr[tempJ];
            }
            subtractValue += tmp;
        }
        sum -= 2 * subtractValue;
        
        arr[qIdx] = -arr[qIdx]; 
        // 다음 쿼리에 영향을 미칠 수도 있어서
        // 실제로도 값에 -1을 곱해준다.
        cout << sum << '\n';
    }
}