[백준 2167] 2차원 배열의 합 - python

https://www.acmicpc.net/problem/2167

2167번: 2차원 배열의 합

 

문제 풀이

• 처음엔 구현으로 풀었다
• 간단히 i-1부터 x까지, j-1부터 y까지 for문을 돌려 합을 구했다

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]

k = int(input())
for _ in range(k):
    i, j, x, y = map(int, input().split())
    count = 0
    for a in range(i-1, x):
        for b in range(j-1, y):
            count += lst[a][b]

    print(count)

 

누적합 풀이

• lst를 입력받고 dp테이블을 만들어 준다
• dp테이블에 lst해당값 + dp의 왼쪽값 + dp의 위쪽값 - dp의 대각선위값을 넣는다

lst

dp

• 예를 들어 dp[2][2]를 구하기 위해서는 lst[1][1](16) + dp[2][1](좌:9) + dp[1][2](위:3) - dp[1][1](대각선위:1)을 해주면 된다
• dp[1][1]을 빼는 이유는 dp[2][1]의 누적합을 구할 때 dp[1][1]을 더했었고, dp[1][2]를 구했을 때도 dp[1][1]을 더했었기 때문에 dp[2][1] + dp[1][2]을 하게 되면 2(dp[1][1])이 더해지기 때문에 dp[1][1]을 빼주는 것이다
• 결과값을 구할 때는 누적합을 이용하여 값을 구한다
• 아래 테이블에서 보면 전체의 누적합은 끝에있는 값일 것이다 하지만 시작이 dp[2][3]같이 중간부터 시작한다면 계산이 복잡해진다
• 아래 테이블로 예를 들자면 i, j, x, y가 2, 3, 3, 4인 경우 x, y까지의 누적합에서 (dp[3][4]) 범위에 들어오지 않는 값을 빼줘야한다 (1, 1)에서 (3, 2)까지 누적합(dp[3][2])와 (1, 1)에서 (1, 4)까지 누적합(dp[1][4])를 빼고, 겹치는 부분인 (1, 1)부터 (1, 2)까지 누적합값(dp[1][2])을 더해준다

 

# 누적합 풀이
n, m = map(int, input().split())
lst = []
dp = [[0]*(m+1) for _ in range(n+1)]
for _ in range(n):
    lst.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, m+1):
        # print(lst[i-1][j-1], dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
        # dp[i=1][j-1]은 dp[i][j-1]과 dp[i-1][j]의 누적합을 구할 때 사용됐으므로
        # 2번 더해지므로 한번 빼줌 (본래값 + 왼쪽 + 위쪽 - 대각선)
        dp[i][j] = lst[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
k = int(input())
for _ in range(k):
    i, j, x, y = map(int, input().split())
    # dp[x][j=1]과 dp[i-1][y]에서 겹치는 부분 dp[i-1][j-1] 더해주기
    print(dp[x][y] - dp[x][j-1]-dp[i-1][y]+dp[i-1][j-1])