kingsubin

BOJ)1915 - 가장 큰 정사각형 본문

PS/boj

BOJ)1915 - 가장 큰 정사각형

kingsubin 2022. 9. 25. 12:46
  • 정사각형의 조건 검사하자는 걸로 접근: 정사각형 한 변의 길이가 짝수, 홀수로 구분하여 정사각형의 중심을 기준으로 생각, 가능하려면 적어도 인접한 두 지점이 1이어야 함.
  • 중간까지 시도 하다가 너무 복잡해지고 접근을 잘못한 거 같단 생각 들고 못 품.
  • 다른 답변 보고 제출했는데 나중에 비슷한 문제 똑같이 풀 수 있을지 모르겠음..

 

  • 변의 길이가 1 보다 큰 정사각형 안에는 그보다 작은 정사각형이 있음.
  • dp 생각, 점화식 세우기
  • dp(i, j) = i, j 를 우하단으로 하는 정사각형의 최대 변 길이
  • dp(i, j) = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
n, m = map(int, input().split())
board = [input() for _ in range(n)]
dp = [[0] * m for _ in range(n)]

for j in range(m):
    if board[0][j] == '1':
        dp[0][j] = 1

for i in range(1, n):
    if board[i][0] == '1':
        dp[i][0] = 1

    for j in range(1, m):
        if board[i][j] == '1':
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

ans = 0
for i in range(n):
    ans = max(ans, max(dp[i]))

print(ans ** 2)

 

 


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

 

'PS > boj' 카테고리의 다른 글

BOJ)1389 - 케빈 베이커의 6단계 법칙  (0) 2022.09.24
BOJ)15686 - 치킨배달  (0) 2022.09.22
boj)2250 - 트리의 높이와 너비  (0) 2020.12.12
boj)1991 - 트리 순회  (0) 2020.12.11
boj)7562 - 나이트의 이동  (0) 2020.12.10
0 Comments
댓글쓰기 폼