[백준/Python] 11660 구간 합 구하기 5

문제: https://www.acmicpc.net/problem/11660

 

 

사용 알고리즘: DP, 누적합

 

 

 

입력받기

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

arr = [[0] * (N+1)]

for i in range(N):
    arr.append([0] + list(map(int, input().split())))

 

위와 같은 모양으로 사용하기 위해 배열의 0 번째 열과 행을 모두 0 으로 초기화 시켰다. 

( 배열의 0 번째 열과 행을 0으로 초기화 시켜놓지 않으면 dp 값을 채울 때 인덱스 에러가 난다 )

 

 

dp 값 채우기

 

dp 의 값은 (i,j) 의 총 누적합이다. 

인덱스 1 부터 사용하기 위해 (N+1)*(N+1) 크기의 dp 배열을 만들었다.

 

합을 구해야할 부분을 아래 그림과 같이 구했다. 

 

전체 - (빼야할 부분1) - (빼야할 부분2) + (더해줘야할 부분)

= dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

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] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]

 

 

이제 for 문을 테스트케이스 수인 M 번만큼 돌면서 결과를 print 하면 된다.

for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
    print(result)

 

 

 

전체코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

arr = [[0] * (N+1)]


for i in range(N):
    arr.append([0] + list(map(int, input().split())))

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] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]

for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
    print(result)