2차원 배열의 합

https://www.acmicpc.net/problem/2167

풀이

  • dp

  • 그림으로 쉽게 풀림

  • 점화식

      s[i][j] = a[i][j] + s[i-1][j] +s[i][j-1] - s[i-1][j-1] 
    
  • ( i,j,x,y 의 구간합 )

      s[x][y] -s[ i-1][y]  - s[x][j-1] + s[i-1][j-1 ]
    

Comments