[백준-파이썬] 11660 : 구간 합 구하기 5

문제 보러 가기!

오늘 카카오 코테를 봤는데, 6번 문제에서 정확성은 다 pass했는데 효율성은 아무것도 통과하지 못했다.ㅠㅠ 접근 방법 자체가 잘못되었다는 것은 알았지만, 어떻게 해야 할지 잘 몰라서 그냥 보내줬다..
끝나고 스터디 팀원분들께 여쭤보니, 이 문제를 좀 응용해서 풀었다고 하셨다..!
누적합 유형(?)이라는데, 나는 이걸 공부해 본 적은 없었다.. 그래서 처음 공부해서 풀어봤다.

주황색처럼 2차원 리스트가 있는데, 보라색 영역의 값들을 다 더하고 싶을 때!
물론 보라색 영역을 한 번만 물어보면, 2중 for문으로 해결할 수 있을 것이다.
하지만 보라색 영역이 바뀌면서, 여러 번 물어볼 때! 그럴 때마다 2중 for문을 돌리면 너무 시간이 오래 걸린다.

그럴 때 이 누적합 방법을 써주면 된다고 한다.
일단 다른 2차원 리스트에 원래 리스트의 값을 다 가로 쭉~ 세로 쭉~을 다 누적해서 더해준다.
그리고 이 누적합 리스트를 활용해서, 보라색 영역의 값의 합을 구할 수 있다.

보라색 영역의 값들의 합 = 빨간 영역 - 노란 영역(A) - 초록 영역(B) + (파란색 칠한 부분)을 해주면 된다.!!
노란 영역과 초록 영역이 겹쳐서, 겹치는 부분을 두 번 빼주니까 한 번 더해주는 것이다.

import copy
N, M = map(int, input().split())
arr = [[0]*(N+1)] + list([0]+list(map(int, input().split())) for _ in range(N))

# 누적합 구하기
arr_sum = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        arr_sum[i][j] = arr_sum[i][j - 1] + arr[i][j]

new_sum = copy.deepcopy(arr_sum)
for i in range(1, N+1):
    for j in range(1, N+1):
        new_sum[i][j] = new_sum[i-1][j] + arr_sum[i][j]

#해당 부분의 합 구하기
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    ans = new_sum[x2][y2] - new_sum[x1 - 1][y2] - new_sum[x2][y1 - 1] + new_sum[x1 - 1][y1 - 1]
    print(ans)

처음에는 누적합을 구할 때는
한줄씩 왼-> 오 더하기
그 후에 위-> 아래 더하기를 했다.
그랬더니 시간초과가 나왔다.ㅠ
좀 더 생각해보니까, 각각 부분의 누적합을 구할 때도 위의 공식(?)을 비슷하게 활용할 수 있었다.
arr_sum[i][j] = arr_sum[i-1][j] + arr_sum[i][j-1] - arr_sum[i-1][j-1] + arr[i][j]
i, j 위치까지의 누적합은 i-1, j까지의 누적합과 i, j-1까지의 누적합을 더하고, 그 둘에서 겹치는 부분(i-1,j-1까지의 누적합)을 빼준 후에, i, j 부분의 값을 더하면 된다!

아래 코드는 이를 반영해서 완성한 코드이다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[0]*(N+1)] + list([0]+list(map(int, input().split())) for _ in range(N))

# 누적합 구하기
arr_sum = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        arr_sum[i][j] = arr_sum[i-1][j] + arr_sum[i][j-1] - arr_sum[i-1][j-1] + arr[i][j]

# 해당 부분의 합 구하기
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    ans = arr_sum[x2][y2] - arr_sum[x1 - 1][y2] - arr_sum[x2][y1 - 1] + arr_sum[x1 - 1][y1 - 1]
    print(ans)