[백준][Java] 17128 - 소가 정보섬에 올라온 이유

목차

 

문제 정보

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

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

난이도 : S2

유형 : 누적합

시간 : O(N + Q)

 

---

문제 풀이

전체합 S는 부분합 N개로 구성된다.

각 부분합은 1~4 , 2 ~ 5... 등 연속된 4개의 수의 곱이다.

 

쿼리로 주어진 소의 번호를 기준으로 하위 연속된 숫자 4개에 해당하는 부분합에 각각 -1을 곱해준 뒤 전체합에 두 번 더해주면 된다.

두 번 더해주는 이유 :

기존값 = a + b + c    ->  c가 -c로 변경 ->  a + b + c - c -c   =>   a + b -c

 

전체 소 8마리

쿼리 : 2번 소  -> 변경해야 할 부분합 2 , 1 , 8, 7

전체합 변경 : 전체합 + ( 2 x 부분합[2번 소] x -1 )... + ( 2 x 부분합[7번 소] x -1 )

 

주의 : 쿼리 연산 중 소의 번호가  1 ~ N의 범위를 넘어갈 때 다시 번호를 알맞게 조절해줘야 한다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * BOJ_17128
 * author_devteo77
 */

public class Main {

    int N;
    int Q;
    int[] cows;
    int[] preSum;
    int res;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        cows = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            cows[i] = Integer.parseInt(st.nextToken());
        }

        preSum = new int[N + 1];
        res = 0;
        for (int i = 1; i <= N; i++) {
            int temp = 1;
            for (int j = 0; j < 4; j++) {
                int idx = i + j;
                if (idx > N) {
                    idx -= N;
                }
                temp *= cows[idx];
            }
            res += temp;
            preSum[i] = temp;
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < Q; i++) {
            int query = Integer.parseInt(st.nextToken());
            for (int j = 0; j < 4; j++) {
                if (query < 1) {
                    query += N;
                }
                preSum[query] *= -1;
                res += (preSum[query] * 2);
                query--;
            }
            sb.append(res).append('\n');
        }

        System.out.print(sb);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}