[백준 BOJ][DP] 16507 어두운 건 무서워

16507_어두운 건 무서워

링크

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

 

풀이

 

http://jaemin8852.tistory.com/194  -  2차원 배열의 합

이 문제와 유사한 방법으로 풀 수 있습니다.

 

(1,1)부터 (n,m)까지의 합을 구해 DP[n][m]에 저장해 놓고, 그걸 활용해 구간의 합을 구할 수 있죠.

구간의 합을 구한 다음, 가로와 세로의 길이 곱으로 나누어 출력하면 됩니다.

합이 1000*1000*10000까지 나오기 때문에 배열의 자료형은 long long으로 해야 합니다.

 

 

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

//16507_어두운 건 무서워 #include <cstdio> using namespace std;   long long DP[1001][1001]; int r, c, k, i, j, x, y, tmp;   int main() {       scanf("%d %d %d", &r, &c, &k);     for (int i = 1; i <= r; ++i) {         for (int j = 1; j <= c; ++j) {             scanf("%d", &tmp);             DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + tmp;         }     }       while (k--) {         scanf("%d %d %d %d", &j, &i, &y, &x);         printf("%lld\n", (DP[y][x] - DP[y][i - 1] - DP[j - 1][x] + DP[j - 1][i - 1]) / ((y-j+1)*(x-i+1)));     }       return 0; } Colored by Color Scripter

cs