백준 19951 : 태상이의 훈련소 생활 (Python)

본문 링크

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
L=list(map(int,input().split()))

dp=[0]*(N+1)
for i in range(M):
    a,b,k=map(int,input().split())
    dp[a-1]+=k ; dp[b]-=k

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

for i in range(N):
    L[i]+=dp[i]

print(*L)

📌 어떻게 접근할 것인가?

예제입력을 보면 과정은 어렵지 않은 문제이다.
다만 N,M 범위가 $1 ≤ N ≤ 100,000$ , $1 ≤ M ≤ 100,000$ 이라는 점이다.
즉 $O(N^2)$ 으로 풀이를 한다면 시간초과 발생한다.
총 $M$ 번의 흙을 옮기는 일을 한번에 할 수 없을까?

📌 첫번째 접근

먼저 누적합을 사용하였다.

$M$ 개의 일을 받을 리스트 $L$ 을 선언해주었다.

예제 입력처럼

• $[[1,5,-3]$ , $[6,10,5]$ , $[2,7,2]]$

을 입력받았다면

시작순서대로 정렬 해준다. 따라서

• $[ [1,5,-3]$ , $[2,7,2]$ , $[6,10,5]]$

위와 같은 리스트가 만들어진다.
이후 인덱스 $i=0$ 을 선언해주고 $0$ 부터 $N-1$ 까지 $1$ 씩 증가한다.

만약 $L[0][1]$ , 즉 가장 왼쪽원소의 시작값이 $i$ 와 같다면 끝값과 높이를 저장한 후에 가장 왼쪽의 원소를 삭제한다. 이때 count 변수에 누적합을 해야할 값을 $L[0][2]$ 로 추가를 해준다.

즉 정렬을 해주고 $i$ 값에 따라 높이를 더하고 끝값을 저장한 배열을 매번 체크해줌으로써 다시 높이를 빼줌으로써 시간복잡도를 줄인다.

다만 이렇게 제출하니깐 바로 틀렸다고 나왔다.. 이론은 맞는거같은데 코드부분에서 실수를 한것같다.

따라서 두번째 접근을 할려고 한다.

📌 두번째 접근

이 방법론은 누적합을 공부한다면 꼭 알았으면 하는 방법론이다. 아주 유용하게 쓸수 있기 때문에다.

a부터 b까지 H 값을 더하는 쿼리가 여러개 있다면 어떻게 처리할것인가?

먼저 인덱스를 기준으로 $a,b,H$ 값이 $0,3,2$ 가 주어졌다고 하자.

먼저 $dp$ 배열을 0으로 초기화 한다.

• $dp=[0,0,0,0]$

이후 시작점에 2를 더하고 끝점에 2를 뺀다.

• $dp=[2,0,0,-2]$

이제 이 $dp$ 배열을 누적합을 시켜보자.

• $dp=[2,2,2,0]$

신기하지않은가?
중요한것은 이것이 쿼리가 몇개가있든간에 시작점과 끝점에 값을 더해주거나 빼고
마지막에 한번 누적합을 해주면 매번 누적합을 한 값과 일치하다는 것이다.

따라서 코드에서

• $dp[a-1]+=k$ ; $dp[b]-=k$
• $dp[i]+=dp[i-1]$
• $L[i]+=dp[i]$

이 3과정만 해주면 문제를 해결할 수가있다.

아주 중요한 방법론이니 꼭 기억하자.