파이썬) 백준 알고리즘 | 17128번 : 소가 정보섬에 올라온 이유

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

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

문제

소 N마리가 정보섬에 올라왔다!

소들은 정보섬 1층 앞마당에서 A1, A2, A3, ..., AN, A1의 순서대로 동그랗게 앉아 쉬고 있다. 각 소들에게는 품질 점수 Ai가 적힌 스티커가 붙어 있다. 욱제는 소 떼 옆에서 효빈이가 계산해 둔 어떤 계산 식을 발견했는데, 그것은 아래와 같다.

 단S=∑i=1N(Ai×Ai+1×Ai+2×Ai+3)  (단, AN+1=A1,AN+2=A2,AN+3=A3)$S = \sum_{i=1}^N(A_{i}×A_{i+1}×A_{i+2}×A_{i+3}) \ \  (단,\ A_{N+1}=A_{1}, A_{N+2}=A_{2}, A_{N+3}=A_{3})$ 

풀어 쓰자면, 원형으로 둘러 앉은 소들에 대해서, 연속한 네 마리 소들의 품질 점수를 곱한 값을 모두 (정확히 한 번씩) 더한 것이다.

욱제는 효빈이가 학교를 떠나지 못하도록 심술부릴 작정이다. 욱제는 총 Q번에 걸쳐 어떤 i번째 소를 선택할 것이다. 그러고는 Ai가 적힌 스티커를 떼어내고, Ai*(-1)이 적힌 스티커를 붙일 작정이다. 그러면 효빈이는 Q번에 걸쳐서 S를 다시 계산해야 한다. 한 번 바꾼 스티커는 다음에 또 다시 바꾸지 않는 이상 계속 유지된다.

     

효빈이의 절친인 당신은 악동 욱제에게 괴롭힘 받는 효빈이를 도와 주기로 했다. 효빈이를 도와 S를 계산해 보자!

입력

첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. (4 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000)

둘째 줄에 N마리 소들의 품질 점수 Ai가 순서대로 주어진다. (1 ≤ |Ai| ≤ 10)

셋째 줄에 욱제가 장난칠 Q개의 소의 번호가 순서대로 주어진다. (1 ≤ Qi ≤ N)

출력

Q개의 줄에 걸쳐 다시 계산된 S의 값을 출력한다.

백준 17128 '소가 정보섬에 올라온 이유' 문제입니다.

사실 이 문제는 for loop으로 단순히 구현했었는데 시간초과가 계속 떠서

다른 분 꺼 보고 작성하였습니다.

저는 매번 곱하게 작성하였는데

먼저 계산하는 것이 시간문제를 해결할 수 있었던 것이었습니다.

import sys
N, Q = map(int, sys.stdin.readline().split())
score = list(map(int, sys.stdin.readline().split()))
numbers = list(map(int, sys.stdin.readline().split()))
pre_score = [0] * N
for i in range(N):
    pre_score[i] = score[i%N]*score[(i+1)%N]*score[(i+2)%N]*score[(i+3)%N]
pre_SUM = sum(pre_score)
for num in numbers:
    for i in range(4):
         pre_score[num-i-1] = -pre_score[num-i-1]
         pre_SUM += 2*pre_score[num-i-1]
    print(pre_SUM)