[ 2023-06-20 🍆 TIL ]

백준 11660번 파이썬

문제

코드

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
n_m = []
n_m_sum = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(n):
  n_m.append(list(map(int, input().split())))
'''
 input == n_m
--------
1 2 3 4
2 3 4 5    
3 4 5 6
4 5 6 7
--------
'''
  
for i in range(1, n+1) :
  for j in range(1, n+1):
    n_m_sum[i][j] = (n_m_sum[i][j-1] + n_m_sum[i-1][j] - 
    n_m_sum[i-1][j-1] + n_m[i-1][j-1])

'''

누적합 == n_m_sum

[0,  1,    1+2,       1+2+3,        1+2+3+4    ]
[0, 1+2, 1+2+2+3,  1+2+3+2+3+4, 1+2+3+4+2+3+4+5]
                   ...생략
                   
n_m_sum[i][j-1] + n_m_sum[i-1][j] 했을 때 중복되는 값인 
n_m_sum[i-1][j-1]을 빼준다.
'''

for _ in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  print(n_m_sum[x2][y2] - n_m_sum[x2][y1-1] - \ 
  n_m_sum[x1-1][y2] + n_m_sum[x1 - 1][y1 - 1])

'''
x2, y2 기준의 큰 사각형에서 제외되는 부분을 제거 해준다. 
(n_m_sum[x2][y1-1]) 세로 사각형 (y1)과 
(n_m_sum[x1-1][y2]) 가로 사각형 (x1)을 제거해주고 
중복 삭제된 사각형( n_m_sum[x1 - 1][y1 - 1]) 을 한번 더해준다.  
'''

어렵다.. 인터넷 찾아서 간신히 이해했다..