풀이 아이디어

입력을 받고
n마리 소의 품질 합 int originSum을 구하고
q번의 장난으로 i번의 품질값에 $(\times-1)$을 해주면

부분 품질합 $P(i)=A(i)\times A(i-1)\times A(i-2)\times A(i-3)$이라면
$P(i), P(i-1), P(i-2), P(i-3)$ 각각이
장난으로 i번 소의 품질 변화에 영향을 받게된다.

• 장난 전 $P(i) = Pb(i)$
• 장난 후 $P(i) = Pa(i)$

인덱스 i값이 변했을 때 영향을 받는 4개 P부분 합 $C(i)$이라면
$C(i) = P(i)+P(i-1)+P(i-2)+P(i-3)$

• 장난 전 $C(i) = Cb(i)$
• 장난 후 $C(i) = Ca(i)$

$Pb(i) = -Pa(i)$이므로
$Cb(i) = -Ca(i)$이다.

장난후 바뀐 품질합이 $changeSum$이라면
$changeSum = originSum - Cb(i) + Ca(i)$
$changeSum = originSum + 2\times Ca(i)$
그러므로 originSum+=2*originQualityList[start]; 이런 식으로 구현했다.

트러블 슈팅

인덱스 보정

인덱스 -1을 n-1로 보정해주기

장난을 쳐서 인덱스 i에 해당하는 값을 $(\times-1)$을 해주면
품질 합 S에 영향을 주는 부분은 A(i)+A(i-1)+A(i-2)+A(i-3)이 된다.
이때 인덱스가 -1이 되면 n-1로 바꿔줘야 의도한대로 동작한다.
예를 들어, n=8이고 장난치는 번호가 3이면
"3 2 1 8"을 입력받았지만
인덱스 계산을 편하게 하기위해 -1씩 해줘서 "2 1 0 7"이고
start=0일 때 start-- 해주면 start=n-1이 되도록 인덱스를 조정해줘야한다.

if(start==0){
	start=n-1;
}
else{
	start--;
}

if, else로 했지만 아래처럼 삼항연산자로 줄일 수도 있다.
start = (start==0) ? n-1 : start-1;
다만 읽을 때 직관적이진 않아서 위에 if, else 방식으로 구현했다.

계산량 줄이기

변하는 부분만 더하고 뺴주기!

위에 오답코드로 제출했을 시간초과가 발생해서 틀렸었는데
그 이유가 소 마릿수 n이 최대 200,000마리가 가능하고
장난친 횟수 q도 최대 200,000번이 가능했는데
장난을 칠 때마다 전체 합을 구한다면 200,000*200,000으로 400억번의 연산을 해야되서
시간초과가 발생했다.
그래서 q번의 장난 중에서 각 장난에서 바뀐 번호 i번에 영향을 받는 부분만 따로 계산해서
원래 품질 총합 - {기존 An} + {바뀐 An}으로 계산해줬다.
이때 장난친 부분은 -1을 곱해주므로 -{기존 An} == {바뀐 An}이 된다.
그래서 원래 품질 총합 + 2{바뀐 An}로 장난으로 값이 변경되어
원래 품질 총합에 변화가 있는 부분만 수정해주면
최대 20만번에서 최대 4번으로 계산량이 확 줄어들게 되어
적은 계산량으로 원하는 값을 구할 수 있게 된다.

오답 코드

q번 장난칠 때마다 새로 다시 계산해주는 방식
최대 $200,000 \times 200,000$번을 계산해야되서 시간초과가 발생한다.

import java.io.*;
import java.util.*;
public class _17128{
    public static void main(String[] args) throws IOException{
        /// 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 소 총 마리수
        int q = Integer.parseInt(st.nextToken()); // 장난칠 횟수
        
        // n마리 소의 품질 점수
        int[] cowsQuality = new int[n]; // 0 ~ n-1
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i <n; i++){
            cowsQuality[i] = Integer.parseInt(st.nextToken());
        }
        
        // 장난칠 Q마리 소의 번호
        int[] kiddingCowNum = new int[q];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < q; i++){
            kiddingCowNum[i] = Integer.parseInt(st.nextToken()) - 1; // 인덱스 조정
        }
        
        /// 계산
        // 원래 소의 품질 합
        int[] originList = new int[n];
        for(int i=0;i<n;i++){
            int partSum = cowsQuality[i]*cowsQuality[(i+1)%n]*cowsQuality[(i+2)%n]*cowsQuality[(i+3)%n];
            originList[i] = partSum;
        }

        // 장난친 소의 품질 합
        for(int i = 0; i < q; i++){
            cowsQuality[kiddingCowNum[i]]*=-1;
            int sumScore = 0;
            for(int j=0;j<n;j++){
                int partSum = cowsQuality[j]*cowsQuality[(j+1)%n]*cowsQuality[(j+2)%n]*cowsQuality[(j+3)%n];
                sumScore += partSum;
            }
            sb.append(sumScore+"\n");
        }
        System.out.println(sb.toString());
    }
}

정답 코드

i번째 소의 품질에 $(\times-1)$을 해주면 영향을 받는 부분만
원래 합에서 더하고 빼주었다.

import java.io.*;
import java.util.*;
public class _17128{
    public static void main(String[] args) throws IOException{
        /// 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 소 총 마리수
        int q = Integer.parseInt(st.nextToken()); // 장난칠 횟수
        
        // n마리 소의 품질 점수
        int[] cowsQuality = new int[n]; // 0 ~ n-1
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i <n; i++){
            cowsQuality[i] = Integer.parseInt(st.nextToken());
        }
        
        // 장난칠 Q마리 소의 번호
        int[] kiddingCowNum = new int[q];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < q; i++){
            kiddingCowNum[i] = Integer.parseInt(st.nextToken()) - 1; // 인덱스 보정
        }
        
        /// 계산
        // 원래 소의 품질 합
        int[] originQualityList = new int[n];
        for(int i=0;i<n;i++){
            int partSum = cowsQuality[i]*cowsQuality[(i+1)%n]*cowsQuality[(i+2)%n]*cowsQuality[(i+3)%n];
            originQualityList[i] = partSum;
        }
        // 원래 품질합 계산
        int originSum = 0; 
        for(int quality: originQualityList){
            originSum+=quality;
        }

        // 장난친 소의 품질 합
        for(int i = 0; i < q; i++){
            int start = kiddingCowNum[i];
            cowsQuality[start]*=-1; // 

            // 변화된 총합계산
            for(int j=0;j<4;j++){ // 4번 반복
                originQualityList[start] = cowsQuality[start]
                                    *cowsQuality[(start+1)%n]
                                    *cowsQuality[(start+2)%n]
                                    *cowsQuality[(start+3)%n];

                // "-기존 품질 = 변화된 품질"이므로
				// "-기존 품질 + 변화된 품질"을 해주기 위해서 
                // "+ 2*변화된 품질"을 해줬다. 
                originSum+=2*originQualityList[start];

                // start = (start==0) ? n-1 : start-1;

                // 인덱스 0에서 -1을 해주면 n-1로 바꿔준다.
                if(start==0){
                    start=n-1;
                }
                else{
                    start--;
                }
            }

            sb.append(originSum+"\n");
        }
        System.out.println(sb.toString()); // 결과값 출력
    }
}