백준[23247] Ten

문제 설명

문제 링크

http://icpc.me/23247

23247번: Ten

풀이

2차원 누적합을 이용하는 문제다.

2차원 누적합을 모른다면 2차원 누적합 설명을 참고해라.

모든 경우를 확인하며 넓이가 300이 되는 경우를 찾으면 된다.

그런데 그냥 찾으면 점 4개의 위치를 고정해야 하므로 O(300^4)일 것 같지만, 시작점 두 개를 고정하고 넓이가 10보다 큰 놈을 만나게 된다면 더 커져도 정답의 후보가 될 수 없는 놈들이기 때문에 확인을 안 해도 된다. 그렇기 때문에 끝 점 두 개는 시작점마다 최대 10개의 경우의 수만 생기게 된다. 그래서 O(NM * 10^2)에 풀 수 있다.

코드

#include <cstdio>

int arr[302][302], psum[302][302];

int main() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
            psum[i][j] = psum[i - 1][j] + psum[i][j - 1] + arr[i][j] - psum[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = i; k <= n; k++) {
                for (int l = j; l <= m; l++) {
                    int sum = psum[k][l] - psum[i - 1][l] - psum[k][j - 1] + psum[i - 1][j - 1];
                    if (sum == 10) ans++;
                    if (sum >= 10) break;
                }
            }
        }
    }
    printf("%d", ans);
}