[BOJ] 백준 2042번 문제 풀이 (Python)

1. 문제 풀이

수의 변경이 빈번히 일어나는 수열의 부분합을 구하는 문제이다.

i 번째 수가 바뀌면 바뀐 크기만큼 i번째 부분합부터 N번째 부분합까지 바꾸는 방법으로 풀 수 있지만 수열의 크기가 $1 \le N \le 1000000$, 중간에 숫자가 바뀌는 횟수가 $1 \le M \le 10000$이기 때문에 최악의 경우 100억번의 연산이 필요해서 다른 방법을 찾아야했다.

최종적으로 $O(M^2+MK)$의 알고리즘을 찾아서 구현하였고 pypy3를 이용해 통과할 수 있다.

• 입력으로 받은 수들의 최초 부분합을 구한다.
• 숫자가 바뀔때마다 최초로 입력받은 숫자에서 얼마만큼 변경되는지를 dictionary에 기록한다.
  • 배열이 아닌 dictionary를 사용한 이유는 $O(M)$ 시간 안에 변경된 숫자들을 이용해 부분합을 구하기 위해서다.
• 변경된 숫자의 차이를 기록한 dictionary를 이용해서 부분합을 구한다.
  • $partialSum[i]$: 입력 받은 수들로 구한 i번째 수까지 최초 부분합
  • $dict[i]$: i번째 숫자에 대해 최초로 입력받았을 때보다 얼마만큼 값이 변경되었는지 기록한 dictionary 값
  • i번째 수까지 부분합: $partialSum[i] + \sum\limits_{j=1}^{i} dict[i]$
    • 실질적으로 dictionaray에 저장된 key의 갯수만큼 반복하기 때문에 $i$번보다 적게 반복한다.
  • b번째 수부터 c번째 수까지 부분합: $partialSum[c] + \sum\limits_{j=1}^{c}dict[j] - partialSum[b-1] - \sum\limits_{j=1}^{b-1}dict[j]$

segment tree라는 것을 이용해 부분합을 더 빠르게 구할 수 있다고 한다. 나중에 찾아서 더 공부해야겠다는 생각이 들었다.

2. 코드

import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

n, m, k = map(int,input().split())
nums = [0] + [int(input()) for _ in range(n)]
partial_sum = [0] * (n+1)
for i in range(1,n+1):
    partial_sum[i] = partial_sum[i-1] + nums[i]
diff = defaultdict(int)

for _ in range(m+k):
    a, b, c = map(int,input().split())
    if a == 1:
        diff[b] = c-nums[b]
    else:
        diff_b, diff_c = 0,0
        for k in diff.keys():
            if k <= b-1: diff_b += diff[k]
            if k <= c: diff_c += diff[k]
        print(partial_sum[c] + diff_c - partial_sum[b-1] - diff_b)