문제
태상이의 훈련소 생활
일렬로 이어진 N개의 칸으로 이루어진 연병장
연병장 각 칸은 1~N번까지 명칭이 붙어있음
조교는 총 M명, 각 조교는 a번 칸부터 b번칸까지 높이 K만큼 흙을 덮거나 파내라고 지시
연병장 각 칸의 최종 높이를 미리 구해 한 번에 일을 수행하고자 한다.
지시를 모두 수행한 뒤 연병장 각 칸의 높이 구하기
n,m <- 100,000 -> N^2안됨.
k >= 0인 경우 a번부터 b번 칸까지 높이가 각각 abs(k)만큼 늘어나도록 흙을 덮어야 한다.
K < 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 abs(k)만큼 줄어들도록 흙을 파내야 한다.
내 코드
import sys
sys.stdin = open("input.txt", "rt")
# 태상이의 훈련소 생활
# 일렬로 이어진 N개의 칸으로 이루어진 연병장
# 연병장 각 칸은 1~N번까지 명칭이 붙어있음
# 조교는 총 M명, 각 조교는 a번 칸부터 b번칸까지 높이 K만큼 흙을 덮거나 파내라고 지시
# 연병장 각 칸의 최종 높이를 미리 구해 한 번에 일을 수행하고자 한다.
# 지시를 모두 수행한 뒤 연병장 각 칸의 높이 구하기
# n,m <- 100,000 -> N^2안됨.
n, m = map(int, input().split()) # 연병장 크기, 조교 수
높이 = [0] + list(map(int, input().split())) # 연병장 각 칸의 높이 -> 1번 인덱스부터 사용하기 위해
지시 = []
for _ in range(m):
a, b, k = map(int, input().split())
지시.append((a,b,k))
# k >= 0인 경우 a번부터 b번 칸까지 높이가 각각 abs(k)만큼 늘어나도록 흙을 덮어야 한다.
# K < 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 abs(k)만큼 줄어들도록 흙을 파내야 한다.
# print(*높이[1:])
change = [0] * (n+2) # 변화량 업데이트
# 연병장 크기는 n, 변화량의 n+1인덱스는 단지 마지막 명령의 종료 지점을 표시하기 위해 필요할 뿐.
for a,b,k in 지시: # 1번 인덱스부터 사용하기 위해.
change[a] += k # 변화 시작
change[b+1] -= k # 변화 종료
# 변화량 누적 및 최종 높이 계산
for i in range(1,n+1):
change[i] += change[i-1]
높이[i] += change[i]
print(*높이[1:])코멘트
처음 생각한건, a칸부터 b칸까지 모두 더해주면서, 모두 빼주면서 값을 축적해 나가야 한다고 생각했다. ( 단순 완탐 ) 하지만 이렇게 하면 시간초과 발생.. -> 이걸 누적합으로 해결 ??
누적합으로 효율적으로 해결하는 방법
1. 변화의 시작화 끝만 표시
- a번 칸에 k를 더한다 (변화 시작)
- b+1번 칸에 k를 뺸다 ( 변화 종료)
- 누적합 계산
- 이렇게 표시된 변화량을 앞에서부터 누적하여 더한다.
ex)
길이 5의 배열에 (2,4,3)이라는 명령 -> 2번부터 4번까지 3 더함
1. 변화량 표시 : [0,3,0,0,-3]
2. 누적합 계산 : [0,3,3,3,0]
이렇게 하면 2번부터 4번까지 3이 더해진 효과를 O(N)의 시간 복잡도로 얻을 수 있다 !!
-> 각 명령을 O(1)시간에 처리하고
-> 최종 결과 계산할 때 단 한번의 순회만으로 모든 변화 적용할 수 있다.
-> O(N+M)이 되어 효율적으로 문제 해결 가능
문제의 핵심은 변화량을 미리 따로 저장해놓고, 이를 이용해 효율적으로 최종 높이를 계산하는 것.
-> 각 작업에 대해 직접 높이를 변경하는 대신, 변화량만 기록하고 이를 누적합으로 계산합으로써 시간 복잡도를 줄일 수 있다.. !
이번 오토에버 코테를 풀며 이런 내용을 알 수 있게 됐다.... 복기 잘 하자 !!
