[파이썬] 백준 11660 : 구간 합 구하기 5 (실버1)

[파이썬] 백준 11660 : 구간 합 구하기 5 (실버1)

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

---

풀이

방향성 생각

• 2차원 누적합을 통해서 중복 영역 계산을 피해준다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
carr = [[0]*(N+1) for _ in range(N+1)]

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

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

코멘트

• 1 2
• 3 4
• 이렇게 생긴 영역에서 4의 값을 구할 때, (4까지 누적합 -3까지 누적합 - 2까지 누적합 + 1까지 누적합)으로 구한다.
• 가장 안쪽에 있는 영역이 두 번 빼지므로 한 번 더해준다.
• 클래스는 귀찮아서 안밀었는데 50점 주길래 다 밀었다~