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

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

로직

recording 함수

• 처음 주어진 소들의 가치 기준으로 각 index에서 값을 구해서 기록(함수 recording)
• 0번 인덱스에는 caws[0]*caws[1]*caws[2]*caws[3]
• 각 인덱스마다 값을 계속 구할 경우 4번의 곱셈 연산이 발생
• 연산을 줄이기 위해 초기값(v)를 구한 후 빠지는 부분과 새롭게 추가되는 부분을 각각 나누고 곱하여 연산을 줄임

solution 함수

• 위에서 구한 record에 장난을 연산하여 출력하는 함수
• total 은 장난치기 전 초기 S값
• 장난친 지점(i)가 바뀔 경우 record에서 i, i-1, i-2, i-3 개의 값에 영향을 끼침 (python에서 인덱스 값이 -일 경우 list의 끝 값부터 계산되는 방식)
• 이를 갱신하며 total 값을 바꿔나감
• total을 갱신하는 이유는 새롭게 S를 구할 경우 record의 길이(N)만큼의 덧셈이 발생
• N이 최대 20만이고 장난도 최대 20만이므로 최대 40000000000 번의 연산 발생
• 이를 줄이기 위해 변경되는 값만 total에 반영

def recording(cnt:int,N:int,caws:list[int])->list[int]:
    value = [0]*N
    v = 1
    for i in range(cnt):
        v *= caws[i]
    value[0] = v
    for i in range(1,N):
        v //= caws[i-1]
        v *= caws[(i+3)%N]
        value[i] = v
    return value

def solution(cnt:int,trick:list[int],record:list[int])->None:
    total = sum(record)

    for i in trick:
        i -= 1
        for j in range(cnt):
            k = i-j
            record[k] = - record[k]
            total += 2*record[k]
        print(total)

N,Q = map(int,input().split())
cnt = 4
caws = list(map(int,input().split()))
trick = list(map(int,input().split()))
record = recording(cnt,N,caws)
solution(cnt,trick,record)