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

19951번: 태상이의 훈련소 생활 (acmicpc.net)

19951번: 태상이의 훈련소 생활

코드

n,m=map(int,input().split())
A=list(map(int,input().split()))
pr_sum = [0 for i in range(n+2)]

for j in range(m):
    a,b,k=map(int,input().split())
    pr_sum[a]+=k
    pr_sum[b+1]-=k
for i in range(n):
    pr_sum[i+1]+=pr_sum[i]
for i in range(n):
    A[i] += pr_sum[i+1]
print(*A, sep=" ")

풀이

처음엔 받는 족족 배열에 저장해서 각각 더하려했다. 이렇게되면 조건 때문에 최대 100,000*100,000 만큼의 연산이 필요하다. 시작과 끝을 아니까, 구간 쪼개듯 풀어볼까도 하였다. 최악의 경우 똑같이 100,000*100,000 만큼의 연산이 필요했다. 누적합을 어떤 식으로 적용할지 고민하다가 조교가 시킨 것에 대해서만 누적합을 사용하면 되겠구나 생각했다. a에 k라고 적고 누적합을 하면 a부터 모든 칸에 k가 들어간다. b까지만 넣고 싶으니 b+1에 -k를 넣으면 a부터 b까진 k, 그 이후로는 아무일도 안일어난다. 모든 명령들을 이렇게 적고 누적합을 돌리면 최종 명령이 된다. 그 다음 처음 받은 배열과 더했다.