백준 11660 구간 합 구하기 파이썬 문제풀이 (python 누적합)

문제 보러가기

 

 

백준 구간 합 구하기 파이썬 문제풀이

문제는 주어진 2차원 배열 안에서 특정 범위의 합을 구하는 문제이다.

범위의 합을 구하는 문제는 누적합으로 접근하면 좋다.

 

n,m = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))
xy = []
for _ in range(m):
    xy.append(list(map(int, input().split())))

# 누적합 구하기 크기는 1칸 더 크게
accum = [[0] * (n+1) for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        accum[i+1][j+1] = arr[i][j] + accum[i][j+1] + accum[i+1][j] - accum[i][j]
for ar in accum:
    print(ar)

먼저 누적합을 구해보자.

잘 나온다.

 

여기서 누적합을 어떻게 이용해서 x1 y1 ~ x2 y2 까지의 합을 구할 수 있는지를 보면

accum(x2,y2) - accum(x2,y1-1) -  accum(x1-1,y2) + accum(x1-1, y1-1)이다.

 

그림처럼 빨간 구역을 구하기 위해서, (파란 범위는 잘못 그린 것)

빨간 구역 바깥에 있는 (x1-1, y2)값 10과 (x2, y1-1) 값 6을 뺀다.

그리고 두 번 뺀 구역 (x1-1,y1-1) 지점 그림에서는 1을 더해준다.

 

이걸 구현하면 된다.

정답 코드

n,m = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))
xy = []
for _ in range(m):
    xy.append(list(map(int, input().split())))

# 누적합 구하기 크기는 1칸 더 크게
accum = [[0] * (n+1) for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        accum[i+1][j+1] = arr[i][j] + accum[i][j+1] + accum[i+1][j] - accum[i][j]

for i in range(m):
    x1 = xy[i][0]
    y1 = xy[i][1]
    x2 = xy[i][2]
    y2 = xy[i][3]
    print(accum[x2][y2] - accum[x2][y1-1] - accum[x1-1][y2] + accum[x1-1][y1-1])

성공적이다.