문제 설명
1. 쉽게 설명하면 2차원 배열에서 [i][j] ~ [x][y] 까지의 합을 구해서 출력하면 되는 문제다.
2. 문제의 데이터가 약해서 naive 하게 풀어도 풀린다.
3. dp 를 이용하면 소요되는 시간을 최소화 시킬 수 있다.
풀이
1. dp 를 이용해서 풀이하는 방법이다.
2. dp[i][j] 를 0,0 ~ i,j 까지의 합이 들어간다고 생각하고 구현하면, 사각형으로 세 구역이 나눠질 수 있다.
3. 문제에서 구하라고 제시한 구역과 그것이 아닌구역(아닌 구역을 2개로 나누면 위, 옆이 된다.) 총 3개
4. 풀이 방법은 0,0 ~ i,j 즉 dp[i][j] 에 나머지 영역을 빼주는 방법이다.
증명
수학적 귀납법
1. dp[1][1] = 항상 n[1][1] 이다.
2. dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + n[i][j] 로 하면 중복된 구역이 중복이 아니게 되고, 나머지 구역들이 더해지게 된다.
3. (2) 로 구해진 dp 배열을 사용해서 (2) 방식으로 구역의 합을 구한다.
코드
문제
2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.
입력
첫째 줄에 배열의 크기 N, M(1≤N, M≤300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 그 다음 줄에는 합을 구할 부분의 개수 K(1≤K≤10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i≤x, j≤y).
출력
K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 32bit-int 범위를 초과하지 않는다.
예제 입력 1
2 3 1 2 4 8 16 32 3 1 1 2 3 1 2 1 2 1 3 2 3
예제 출력 1
63 2 36