[Silver I] 구간 합 구하기 5 - 11660

github

정답 코드

import sys
input = sys.stdin.readline

# 입력 받기
N, M = map(int, input().split())
tables = []

for _ in range(N):
    table = list(map(int, input().split()))
    tables.append(table)

# 2차원 dp 배열 생성 및 누적합 계산
dp = [[0] * (N + 1) for _ in range(N + 1)]

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

# 구간합 계산 함수
def range_sum(x1, y1, x2, y2):
    result = dp[x2][y2]
    if x1 > 1:
        result -= dp[x1 - 1][y2]
    if y1 > 1:
        result -= dp[x2][y1 - 1]
    if x1 > 1 and y1 > 1:
        result += dp[x1 - 1][y1 - 1]
	    return result

sum_list = []
# 쿼리 처리 및 출력
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    sum = range_sum(x1, y1, x2, y2)
    sum_list.append(sum)

for result in sum_list:
    print(result)

틀린 코드

N, M = map(int, input().split())
tables = []

for _ in range(N):
    table = list(map(int, input().split()))
    tables.append(table)

dp = [[0] * N for _ in range(N)] # 2차원 리스트
for i in range(0, N):
    for j in range(0, N):
        if i == 0 and j == 0:
            dp[i][j] = tables[i][j]
        elif j == 0:
            dp[i][j] = dp[i-1][N-1] + tables[i][j]
        else:
            dp[i][j] = dp[i][j-1] + tables[i][j]

def range_sum(x1, x2, y1, y2, dp):
    if x1 == x2 and y1 == y2:
        return tables[x1-1][y1-1]
    elif x1 == 1 and y1 ==1:
        return dp[x2-1][y2-1]
    else:
        sum = dp[x2-1][y2-1] - dp[x1-1][y1-1]
        return sum

range_sum_list=[]
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    range_sum_list += [range_sum(x1, x2, y1, y2, dp)]

for sum in range_sum_list:
    print(sum)

특정 구간 [x1, y1]부터 [x2, y2]까지의 합을 구할 때 중복된 구간을 제거해야 하는데, 현재 코드에서는 dp 배열에서 위쪽, 왼쪽, 그리고 좌상단 구간을 포함한 계산을 하지 않기 때문에 잘못된 결과가 나옵니다.

누적합 자체를 잘못 구했음

dp

range sum