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

백준 11660_구간 합 구하기5

조건

• NxN 개의 수가 NxN 크기의 표에 채워져 있다.
• (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램 작성하시오

입력

• 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)
• 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다.
• 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다.
• 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

# 접근 방법

• 단순 슬라이싱을 통해 풀면 시간초과가 발생한다.
• 현재 좌표를 (0,0)에서 시작한 사각형의 오른쪽 아래 꼭지점으로 하는 dp table을 이용하여 누적 합을 구해주면 된다.
  • 이 때, dp 인덱스를 +1 씩 해주면 더 풀기 편하다.
• 현재 좌표의 값은 dp[i-1][j] + dp[i][j-1] 값에 2번 더해진 dp[i-1][j-1]을 빼주면 된다.
• 이후 원하는 구간 값을 출력할 때도 비슷하다.
  • 주어진 구간 사각형의 바로 직전 행의 누적 합과 직전 열까지의 누적 합을 빼주고, 두 번 빼진 i-1, j-1 값을 더해주면 된다.

시간초과

import sys
input = sys.stdin.readline

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

arr = [[*map(int, input().split())] for _ in range(N)]

for i in range(M):
    result = 0
    x1, y1, x2, y2 = map(int, input().split())
    while x1-1 <= x2-1:
        result += sum(arr[x1-1][y1-1:y2])
        x1 += 1

    print(result)

DP 이용 통과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, M = map(int, input().split())  
# 첫 행, 첫 열에 0으로 채워서 한줄 추가  
nums = [[0] * (N+1)] + [[0] + [*map(int, input().split())] for _ in range(N)]  

# 누적 합을 구해주는데 각 행마다가 아닌 현재 좌표를 사각형 오른쪽 아래로 가정하고 구하기  
# 2, 3의 경우 1, 1에서 2, 3까지의 누적합  
# dp의 바로위, 바로 왼쪽을 더해주고  
# 두번 더해진 왼쪽 대각선 위를 빼주고  
# nums의 현재 좌표 더해주면 됨  
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] + nums[i][j]  

# 주어진 좌표 dp 값에서 바로 직전열의 값과 직전 행의 값을 빼주면 됨  
# 2,2 에서 4, 4의 경우  
# dp[4][4] 값에서 dp[1][4], dp[4][1] 빼주고 2번빼진 dp[1][1]을 더해주면 된다.  
for _ in range(M):  
    a, b, c, d = map(int, input().split())  
    result = 0  
    print(dp[c][d] - dp[a-1][d] - dp[c][b-1] + dp[a-1][b-1])