백준 14309, Safe Squares (Large)

개요

문제 링크
골드 5, DP

2차원 배열 내에서 0으로 이루어진 정사각형의 개수

---

접근

1. 한 변의 길이가 여러 개인 정사각형을 모두 세 주어야 하는데 그럼 O(n^2)을 넘어가지 않나? 하고 생각.

2. 일단 dp를 쓰고 O(n^2)안에 해결하는 방법은 인접한 것들만 봐줘야 하는데, 어디까지 보냐가 핵심.

3. dp에 저장할 내용은 왼쪽 위부터 만들어 내려올 수 있는 최대 정사각형의 길이 이게 되는 이유는 (x,y)까지의 최대 길이가 곧 (x,y)를 오른쪽 아래점으로 포함하는 정사각형의 개수가 됨. 왜냐하면 최대 길이 정사각형 내부에서는 모두 정사각형을 만들 수 있으니까.

4. 왼쪽이랑 위는 반드시 봐줌. 최대 정사각형은 왼쪽과 위에서 만든 정사각형을 반드시 포함하기 때문. 이때 아래 케이스를 보자

   011
   112
   12?

   ?에 들어갈 값이 2인 것은 머리로 알 수 있다. 하지만 왼쪽과 위만 비교하면 3을 출력하므로 왼쪽위까지 비교해야 한다.

---

Pseudo code

for (y = 세로)
    for (x = 가로)
        if (!dp[y][x])
            continue;
        dp[y][x] = min(왼,위,왼위)+1

---

Source code

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;
using ld = long long;
ld dp[N][N];
ld test() {
    int r, c, k;
    cin >> r >> c >> k;
    int x, y;
    for (int i=0; i<r; i++)
        for (int j=0; j<c; j++)
            dp[i][j] = 1;
    for (int i=0; i<k; i++) {
        cin >> y >> x;
        dp[y][x] = 0;
    }
    for (int i=1; i<r; i++)
        for (int j=1; j<c; j++) {
            if (!dp[i][j])
                continue;
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1;
            dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
        }
    ld sum = 0;
    for (int i=0; i<r; i++)
        for (int j=0; j<c; j++)
            sum += dp[i][j];
    return sum;
}

int main() {
    int t;
    cin >> t;
    for (int i=1; i<=t; i++)
        printf("Case #%d: %lld\n",i,test());
}