[알고리즘][Python] 백준 11660 구간 합 구하기 5 문제 풀이

문제 출처 : www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

---

문제 해석 : 주어진 x1,y1 ~ x2,y2 사이에 존재하는 수의 합을 구하는 문제이다.

 

문제 풀이 : 일반적으로 합을 하나 하나씩 더해서 구했을 경우 시간 초과가 나기 때문에 DP를 통해서 문제를 풀어줘야한다. x,y 까지의 합을 구한 테이블을 이용해서 매 결과를 +,- 연산을 이용해서 구하면 풀 수 있다.

---

풀이 코드

import sys
input = sys.stdin.readline

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

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

for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            continue
        elif i == 0:
            dp[i][j] = dp[i][j - 1] + arr[i][j]
        elif j == 0:
            dp[i][j] = dp[i - 1][j] + arr[i][j]
        else:
            dp[i][j] = sum(arr[i][:j]) + dp[i - 1][j] + arr[i][j]

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == 1 and y1 == 1:
        answer = dp[x2 - 1][y2 - 1]
    elif x1 == 1:
        answer = dp[x2 - 1][y2 - 1] - dp[x2 - 1][y1 - 2]
    elif y1 == 1:
        answer = dp[x2 - 1][y2 - 1] - dp[x1 - 2][y2 - 1]
    else:
        answer = dp[x2 - 1][y2 - 1] - dp[x1 - 2][y2 - 1] - dp[x2 - 1][y1 - 2] + dp[x1 - 2][y1 - 2]
    print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.