Algo

백준 4095. 최대 정사각형

문제 링크

아이디어 및 회고

nxm 행렬 1로 이루어진 가장 큰 정사각형 찾기 그때의 한 변의 길이 찾기

0 1 0 1 1
1 1 1 1 1
0 1 1 1 0
1 1 1 1 1

0 1 0 1 1
1 1 1 1 1
0 1 2 2 0
1 1 2 3 1

0, n 또는 n, 0은 그대로 map에 있는 값으로 초기화

내 위치가 i, j라고 하면

i-1, j
i, j-1
i-1, j-1 의 수가 전부 같으면 (0을 제외한) 그 수에 +1

• 0이면 -> 0
• 0이 아닌 자리에 좌표에 대해:
  • 만약 3개 중에서 1개라도 0이면 그 자리는 1로 자기 자신이 됨
  • 모두 0이 아님 && 모두 같은 수 => 그 수에 +1 하면 됨
  • 모두 0이 아님 && 하나라도 다른 수 => 가장 작은 수에 +1
• 놓쳤던 지점
  • dp 배열에서 마지막행에 무조건 답이 있을 거라는 고정관념;;