[Python] 11660번 구간 합 구하기 5, 그림 참조

✏️ 문제

문제 파악

dp 배열을 주어진 배열의 누적 합을 담는 배열로 정의한 후 각 배열에 대해 그림으로 작성하면 다음과 같이 나온다.

코드에 대해서 너무 헷갈려서 IndexError가 계속 났다..

ary 배열은 0부터, dp 배열은 1부터 시작하는 것을 잊지 말자... 두 개가 각각 index 0, 1부터 시작하지 않으면 코드가 매~우 길어져요...

 

 

알고리즘

• 다이나믹 프로그래밍 
• 누적 합

 

코드

• 시간 초과 코드

처음엔 그냥 단순하게 풀어봤지만 틀렸다. 당연함. 실버 1문제임.

n, m = map(int, input().split())
ary = [list(map(int, input().split())) for _ in range(n)]

for _ in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  num = 0

  if x1 == x2 and y1 == y2:
    num += ary[x1-1][y1-1]
  else:
    for i in range(x1-1, x2):
      for j in range(y1-1, y2):   
        num += ary[i][j]

  print(num)

• 통과 코드 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ary = [list(map(int, input().split())) for _ in range(n)]
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][j-1] + dp[i-1][j] - dp[i-1][j-1] + ary[i-1][j-1]
    
for k in range(m):
  x1, y1, x2, y2 = map(int,input().split())
  
  num = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
  print(num)