Prefix Sum

문제 링크 https://www.acmicpc.net/problem/21758 문제 해설 Idea 벌이 같은 방향을 향하는 경우 상자까지의 총합에서 두 벌의 시작 위치에 있는 값을 제외 벌이 다른 방향을 향하는 경우 상자까지의 총합에 절댓값을 취해서 더함 Data Size N: 3 <= int <= 100,000 arr[i]: 1 <= int <= 10,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 N = int(input()) arr = list(map(int, input().split())) forward, backward = [arr[0]]+[0]*(N-1), [0]*(N-1)+[arr[-1]] for i in range(1,N): forward[i] = forward[i-1] + arr[i] backward[N-i-1] = backward[N-i] + arr[N-i-1] answer = 0 for i in range(1,N-1): answer = max(answer, forward[N-1]*2-forward[0]-forward[i-1]-arr[i]*2) answer = max(answer, backward[0]*2-backward[N-1]-backward[N-i]-arr[N-i-1]*2) answer = max(answer, forward[i]-arr[0]+backward[i]-arr[-1]) print(answer)

문제 링크 https://www.acmicpc.net/problem/21318 문제 해설 Idea Prefix Sum 실수한 곡에 대한 누적합을 구하고 인덱싱을 통해 특정 구간에 대한 누적합 출력 마지막 곡은 항상 성공하기 때문에 y에 대한 누적합과 y-1에 대한 누적합이 다르면 1 감소 Time Complexity Prefix Sum: O(N) = 100,000 Data Size N: 1 <= int <= 100,000 scores: int(10^9) * N Q: 1 <= int <= 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys input = sys....