2167 구현, 누적합, DP

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

2167번: 2차원 배열의 합

import sys
input= sys.stdin.readline
##(i,j)~~(x,y)위치까지 저장 되어있는 수들의 합을 구하라
#1. 입력 받고
#2. 배열 만들고
#3. k입력받고 슬라이스 해서 넣고

N,M = map(int, input().split(' '))
arr1 = [list(map(int,input().split(' '))) for _ in range(N)]
K=int(input())    
#arr2 = [list(map(int,input().split(' '))) for _ in range(K)]
#arr=[[1,2,4],
#     [8,16,32]]
#print(arr[0][0]~arr[1][3])
#걍 이중포문 쓰자.
#print(arr2)
#print(arr2[2][0])
#print(type(arr2[2][2]))
for _ in range(K):
    result=[]
    #print(_)
    cnt=0
    i,j,x,y = map(int,input().split(' '))
    for a in range(i-1,x):
        #print(i)
        for b in range(j-1,y):
            cnt+=arr1[a][b]
            #result.append(arr1[a][b])
    #print(sum(result))
    print(cnt)

append도 시간이 은근 걸린다!

그리고 바보같은 실수를 해서 시간이 오래걸렸다.

컴퓨터는 틀리지 않았다.

내가 틀린것이다.

틀린 것을 알았다면 고치면된다!!

 

 

그리고 몰랐는데 dp로 많이 접근하는 것 같았다. 아무래도 시간초과때문인것으로 보임

# 배열의 크기 입력
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

# 부분의 개수 입력
K = int(input())
dp = [[0] * (M+1) for _ in range(N+1)]

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

for _ in range(K):
    i, j, x, y = map(int, input().split())
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])