[백준] 11660번: 구간 합 구하기 5 - python

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

11660번: 구간 합 구하기 5

 

처음 아이디어

 

무지성 더하기를 작성.. 당연히 안된다..

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

for _ in range(m):
    sum = 0
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(x1-1, x2):
        for j in range(y1-1, y2):
            sum+=arr[i][j]
    print(sum)

 

두번째 아이디어

 

구간 합을 이용하여 계산한다.

사실 이 부분은 패턴찾기가 너무 어려워서 애를 많이 먹었다. 

 

값을 찾을 수 있는 패턴을 찾아 점화식을 세운 다음 코드를 작성한다.

 

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = []
dp = [[0] * (n+1) for i in range(n+1)]
for _ in range(n):
    arr.append(list(map(int, input().split())))


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-1][j-1]


for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1])
    print(dp[x2][y2])
    print(dp[x1-1][y2])
    print(dp[x2][y1-1])
    print(dp[x1-1][y1-1])
    for k in range(1,n+1):
        for k2 in range(1, n+1):
            print(dp[k][k2], end=" ")
        print()

 

겨우 print하면서 작성 완료...