https://www.acmicpc.net/problem/19951
공부 날짜 : 2023.02.03
정답 참조 여부 : X
연병장의 특정구간에 흙을 파내거나 채워넣을 때 m번의 명령 수행후 연병장의 결과를 출력하는 문제이다.
누적합 문제의 개념이 구간합을 빠르게 구한다는 느낌으로 받아들이고 있었는데, 이런식으로 적용도 가능하다는걸 알았다.
조교의 명령에 의해서 땅의 변화가 시작되는 위치에 k만큼 더해주고 이번 명령으로 변화가 끝나는 위치 +1 째 위치에 -k를 해서 조교의 명령을 하나의 리스트로 저장했다.
그 다음 조교의 명령을 누적합으로 저장하며 현재 연병장의 높이에 조교의 명령에의한 결과를 출력하도록 했다.
쉬운 유형으로 응용해볼 수 있었어서, 나쁘지 않았다. 어려운 유형에서 문제가 제시 되었으면 아마 아이디어를 떠올리지 못하고 헤맸을거 같다.
소스코드
import sys
input = sys.stdin.readline
##############################################
n, m = map(int, input().split())
ground = list(map(int, input().split()))
# 조교의 명령을 저장하는 리스트
order_answer = [0 for _ in range(n+1)]
# a-1 ~ b-1 까지 조교의 명령대로 수행
# b-1까지 k의 변화를 줘야 하므로 b에 저장해야 b-1에서 명령 수행
for _ in range(m):
a, b, k = map(int, input().split())
order_answer[a-1] += k
order_answer[b] -= k
# 땅의 변화를 누적합으로 저장
change = 0
# 땅의 변화를 적용하여 땅의 높이 출력
for i in range(n):
change += order_answer[i]
print(ground[i] + change, end = " ")
