백준 15724. 주지수

tose33 2022. 7. 16. 13:30

15724번: 주지수

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은

www.acmicpc.net

a[][] : 주어지는 숫자

d[][] : [1][1] ~ [r][c] 까지의 수의 합

우선 2차원 배열 d에 d[r][c] = [1][1] ~ [r][c] 까지의 수의 합을 구한다.

d[r][c] = d[r-1][c] + d[r][c-1] - d[r-1][c-1] + a[r][c];

주어지는 r1, c1, r2, c2 에 대하여

[r1][c1] ~ [r2][c2]까지의 합은 = d[r2][c2] - d[r2][c1-1] - d[r1-1][c2] + d[r1-1][c1-1]