문제링크: https://www.acmicpc.net/problem/11660
구간합 문제 Lv.5입니다!
Problem
지난 포스트에서 소개한 Lv.4에서는 일차원 배열을 다루었지만, 이번 포스트에서는 2차원 배열을 다룹니다.
똑같이 구간합을 구하면 되는데, 구간합을 잘 이해해야합니다.
만약, (2,2) 에서 (3,4)까지의 구간합이라면, (2,2)부터 (2,4)까지, 그리고 (3,2)부터 (3,4)까지의 원소를 합해주면 되겠습니다.
테이블을 생각하고 마우스로 드래그한다고 생각하시면 되요!
Approach & Solution
처음에 저는 (2,2) 에서 (3,4)까지의 구간합에 (2,1)도 들어가는줄 알았습니다. 그래서 처음엔 구현을 조금 이상하게 했는데, 계속 예제와 다른 결과가 나오길래, 뭘 잘못 이해했나 싶어서, 예제를 찬찬히 보고 제가 구간합을 잘못 이해했다는것을 찾았습니다.
다시 풀이로 돌아와서, Lv.4 처럼 구간합을 배열에 저장하는 방식으로 접근해야 time limit안에 들어올 수 있습니다. 근데, 저장하는 방식을 잘 설정해야해요.
import sys
input = sys.stdin.readline
m,n = map(int,input().split())
target = [[0]* (m+1)]
for _ in range(m):
temp = [0] + [int(x) for x in input().split()]
target.append(temp)
sum_target = [[0]* (m+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,m+1):
sum_target[i][j] = sum_target[i-1][j] + sum_target[i][j-1] - sum_target[i-1][j-1] + target[i][j]
answer = []
for _ in range(n):
start_x, start_y,end_x, end_y = map(int,input().split())
result = sum_target[end_x][end_y] - sum_target[start_x-1][end_y] - sum_target[end_x][start_y-1] + sum_target[start_x -1][start_y-1]
answer.append(result)
print('\n'.join(map(str,answer)))
SailingToTheMoooon