문제
https://www.acmicpc.net/problem/5549
접근 방식
만약 bruteforce로 해결할 때 최악의 경우 1000 * 1000의 공간을 100000개의 쿼리로 수행하기 때문에 시간 효율적이지 못하다.
쿼리 수 자체가 많으므로 미리 누적합을 캐싱해서 활용하면 쿼리 수행은 O(nm) -> O(1)로 감축된다.
👉 2차원 누적합
2차원 누적합은 1차원과 어떻게 다른가?
1차원 누적합 : prefix_sum[n]은 1번째부터 n번째 까지의 누적합을 말한다.
아래와 같이 값을 누적시키는 방식이다
✅ 누적합 구하기 :
p_sum[i] = p_sum[i - 1] + arr[i]
✅ i1부터 i2까지의 합 구하기 (i1 <= i2) :
p_sum[i2] - p_sum[i1 - 1]
2차원 공간으로 가져와서 생각할 경우, 식이 좀 더 복잡해진다.
2차원 누적합 : prefix_sum[r][c]은 (1, 1)에서 (r, c)까지의 누적합을 의마한다.
p_sum[i][j]의 누적합을 구하기 위해 p_sum[i - 1][j]과 p_sum[i][j - 1]을 더하면 될 것이다. 다만, 겹친 부분(p_sum[i - 1][j - 1])이 있으므로 이를 제외 시켜줘야 이전 누적합이 된다.
✅ 누적합 구하기 :
p_sum[i][j] = p_sum[i - 1][j] + p_sum[i][j - 1] - p_sum[i - 1][j - 1] + arr[i][j]
👇 역시 겹친 공간을 구분해서 처리하면 된다
✅ (i1, j1)부터 (i2, j2)까지의 합 구하기 :
p_sum[i2][j2] - p_sum[i1 - 1][j2] - p_sum[i2][j1 - 1] + p_sum[i1 - 1][j1 - 1]
이때 (i1, j1)에서 (i2, j2)는 포함 - 포함 관계를 가정한다
처음 문제를 풀 땐 별 생각없이 n * m 공간의 누적합을 만들고 처리했는데, (n + 1) * (m + 1) 공간으로 설정하고 처음 가로와 세로를 0으로 초기화 시켜두면 연산하기 편하다.
[x, x, x]는 차례대로 'J'의 누적합, 'O'의 누적합,'I'의 누적합을 의미한다.
코드
import sys
input = sys.stdin.readline
# 누적합을 활용해 연산
def calc(sx, sy, ex, ey):
res = [0, 0, 0]
for k in range(3):
res[k] = p_sum[ex][ey][k] - p_sum[sx - 1][ey][k] - p_sum[ex][sy - 1][k] + p_sum[sx - 1][sy - 1][k]
return res
# 하나의 칸 구하기 -> 'J', 'O', 'I' 각각 연산해서 return
def add(s1, s2, s3, cur):
return [s1[k] + s2[k] - s3[k] + cur[k] for k in range(3)]
# 해당 영역 구분하기
def counter(key):
return {'J': [1, 0, 0], 'O': [0, 1, 0], 'I': [0, 0, 1]}.get(key)
m, n = map(int, input().split())
q = int(input())
MAP = [input() for _ in range(m)]
# 2차원 Prefix Sum -> (n + 1) * (m + 1)으로 수정
p_sum = [[[0, 0, 0] for _ in range(n + 1)] for _ in range(m + 1)] # ['J', 'O', 'I'] 각각의 합
for i in range(m):
for j in range(n):
p_sum[i + 1][j + 1] = add(p_sum[i][j + 1], p_sum[i + 1][j], p_sum[i][j], counter(MAP[i][j]))
# 쿼리 돌면서 누적합 구하기
for _ in range(q):
sx, sy, ex, ey = map(int, input().split())
print(*calc(sx, sy, ex, ey))참고 : 👍 2차원 누적합 설명글
