[알고리즘/동적 계획법] 11660 번 : 구간 합 구하기 5 - python

링크 : https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

---

• 문제
• 소요시간: 실패

---

• 설계하기(접근방법) 

1. n, m, 리스트, 좌표를 입력받는다

2. 알고리즘 해석

직접 모든 경우의 수를 더하면 시간을 초과할 것이다.

따라서 동적 계획법을 통해 누적합 리스트를 구해놓아야 할 것이다.

 

누적합에 따른 일반식은 다음과 같이 나타낼 수 있다

dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i-1][j-1]

즉 dp[i][j]의 왼쪽과 위 항을 더하고, 대각선 항의 누적합을 뺀후, 빠진 대각선의 일반항을 더해준다

 

구하려면

좌표1부터 좌표2의 값은

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

가 된다.

 

3. result를 출력한다.

 

 

 

 

---

• 코드(출력)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

dp = [[0] * (n + 1) for _ in range(n+1)]

arr= []
for i in range(n):
    a = list(map(int, input().split()))
    arr.append(a)

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

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)

---

• 얻어갈 부분

1. 처음에 문제를 잘못 해석해서 코드를 전부 날렸다. 문제를 꼼꼼히 두번씩 읽는 습관을 가지자