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

문제

• 1번 ~ N번까지의 소들이 동그랗게 앉아 있다.
  • 4 <= N <= 200,000
• 각 소들에 품질 점수 스티커가 붙어있고, i번째 소의 품질 점수는  $A_i$이다.
  • 1 <= $|A_i|$ <= 10
• 전체 품질 점수 S는 연속한 네 마리 소들의 품질 점수를 곱한 값을 모두 더한 값이다.
• 욱제가 장난으로 Q번에 걸쳐 i번째 소를 고르고 점수에 -1을 곱한 값으로 바꾼다. 그때마다 다시 계산된 S를 출력해야 한다.
  • 1 <= Q <= 200,000

 

풀이

• Q 번 반복동안, 점수 구하기 O(N) 을 그대로 반복하면 O(QN)으로 시간 초과가 나는 문제
• 누적합 응용
  • 전체 소의 품질 점수를 구한 후, 바뀐 i번째가 해당하는 그룹의 값만큼 +/- 계산해주기
• i 번째 점수가 바뀌면 i-3번 ~ i번 까지의 점수가 바뀌게 된다. 
  • 원형이기 때문에 1~3번째 점수가 N, N-1, N-2번에 영향을 준다는 사실만 주의하자
• 시간 복잡도 : O(4*Q)

 

import sys
input = sys.stdin.readline

N, Q = map(int , input().split())
a = list(map(int, input().split()))     # 소들의 점수
a += a[:4]                              # 마지막 소 점수를 위해 추가
# 각 소의 품질 점수 구하기
score = [0, ]
for i in range(N):
    score.append(a[i]*a[i+1]*a[i+2]*a[i+3])

s = sum(score)  # 전체 품질 점수
# Q번 동안 반복
for x in list(map(int, input().split())):
    # 바뀐 x 번째 소 점수 교체 + 점수 계산
    for i in range(x-3, x+1):
        if i < 1 :
            score[i+N] *= -1
            s += 2*score[i+N]
        else:
            score[i] *= -1
            s += 2*score[i]

    print(s)

 

References

• 백준 17128번
• 2023.04.25 오늘의 문제