11660. 구간 합 구하기 5

스케치

• 구간 합을 참고

기존 코드

import sys  
input = sys.stdin.readline  
  
# n, m 입력  
n, m = map(int, input().split())  
  
# 표 채우기  
a = [list(map(int, input().split())) for _ in range(n)]  
  
# 구간합 표 채우기  
s = [[0]*(n+1) for _ in range(n+1)]  
s[1][1] = a[0][0]  
  
# 1. 1행, 1열 채우기  
for i in range(2, n+1):  
    s[1][i] = s[1][i-1] + a[0][i-1]  
    s[i][1] = s[i-1][1] + a[i-1][0]  
  
# 2. 나머지 채우기  
for i in range(2, n+1):  
    for j in range(2, n+1):  
        s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i-1][j-1]  
  
# 특정 구간합 출력  
for _ in range(m):  
    x1, y1, x2, y2 = map(int, input().split())  
    prefix_sum = s[x2][y2] - (s[x2][y1-1] + s[x1-1][y2] - s[x1-1][y1-1])  
    print(prefix_sum)

최적화 코드

import sys  
input = sys.stdin.readline  
  
n, m = map(int, input().split())
  
# 입력과 동시에 구간합 계산  
s = [[0] * (n + 1) for _ in range(n + 1)]  
  
for i in range(1, n + 1):  
    row = list(map(int, input().split()))  
    for j in range(1, n + 1):  
        s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + row[j-1]  
  
# 특정 구간합 출력  
for _ in range(m):  
    x1, y1, x2, y2 = map(int, input().split())  
    print(s[x2][y2] - (s[x2][y1-1] + s[x1-1][y2] - s[x1-1][y1-1]))

• PEP8 파이썬 Coding Convention에 따라 코드 스타일 수정
• 반복문이 특정행을 기준으로 모든 열이 결정됨
  • 따라서, 행 한 줄 입력과 동시에 구간합을 바로 계산