[백준][Python] 19951 태상이의 훈련소 생활

카카오 블라인드 1차 6번 효율성 문제.

구간 합을 이용해 갱신하는 방법으로 그때 아이디어만 얻어두었다가 드디어 해결했다.

양 끝에만 적어두고 dp로 누적값 배열을 만든 후 최종 배열은 원배열 + 변화량 배열의 합으로만 구하는 방법.

프로그래머스에 이번년도 문제 올라오면 다시 풀어보자.

 

사람들이 웰노운 웰노운 거리더니.. 여튼 좋은 방법론을 얻었다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
H = list(map(int, input().split()))
save = [0] * (N+1)
for _ in range(M):
    a, b, k = map(int, input().split())
    save[a-1] += k
    save[b] -= k

dp = [0] * (N+1)
dp[0] = save[0]
for i in range(1,N+1):
    dp[i] = dp[i-1] + save[i]

for i in range(N):
    print(H[i] + dp[i], end=' ')