[1915] 가장 큰 정사각형 - C++

정말 너무 진이 빠진다ㅏㅏ

---

풀이

정사각형인지 판단하려면 어떻게 해야 할까?

위, 옆, 대각선을 확인하면 된다.

이걸로 이 문제는 해결이라 볼 수 있다.

 

 

점화식

$$\large dp [x][y] = min(\{dp [x-1][y], dp [x][y-1], dp [x-1][y-1]\})$$

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, m;
int arr[1002][1002], dp[1002][1002];
int main(){
  init();
  cin >> n >> m;

  //입력
  for(int i = 1; i <= n; ++i){
    string str;
    cin >> str;
    for(int j = 1; j <= m; ++j){
      arr[i][j] =str[j-1]-'0';
    }
  }
  
  //계산
  int ans = 0;
  for(int x = 1; x <= n; ++x)
    for(int y = 1; y <= m; ++y)
      if(arr[x][y]){
        dp[x][y] = min({dp[x-1][y], dp[x][y-1], dp[x-1][y-1]}) + 1;
        ans = max(ans, dp[x][y]);
      }

  cout << ans * ans;
  return 0;
}

 

그림 설명

왼쪽 = arr

오른쪽 = DP 테이블

1

2

3

4

5

6

7

8

9

10

11

 

어떻게 가능한 걸까?

왜 세 방향 중에서 작은 방향을 고른 후 +1 하는 게 가능한 걸까?

위 그림을 보면 알 수 있듯, $ 3 \times 3 $ 은 불가능 한 것을 알 수 있다.

세 방향 모두 같아야 그다음 크기의 정사각형이 되는 것을 알 수 있다.

 

이게 진정한 다이내믹 프로그래밍이 아닐까.

---

문제를 풀며

오랜만에 고민다운 고민을 해본 문제였다.뭔가 풀릴 듯 말듯한 그 느낌으로 3시간을 생각했다. 

2시간을 넘겼을 때 답을 볼까 고민하다 아... 이만큼 했는데 답을 보는 건 너무 아까워서 계속 고민했던 것 같다.

 

그런데 딱 3시간이 되어 서도 맞히지 못했을 때 그냥 답을 봤다. 이 이상 문제를 끌면 오히려 안 좋을 것 같기 때문이었다.

답을 보고 난 후 내가 지금껏 고민한 코드와 조금, 정말 조금은 닮아 있었기에 억울하진 않았다.