BOJ 1915(가장 큰 정사각형)풀이

solved.ac 티어 : 골 5

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

1915번: 가장 큰 정사각형

dp로 된다는걸 알면 쉬운데 dp인걸 알아채기가 어렵다고 해서 골 5라고 한다.

바로 문제풀이를 설명하자면

dp [i][j]=(i, j) 번째 점을 포함하는 정사각형의 한 변의 최대 길이

이게 끝이다.

dp [i][j]를 구하려면 (i, j) 번째 점이 0일 때는 0이고 1일 때는 (i-1, j)==(i, j-1)==(i-1, j-1) 이면 셋 중 하나의 값+1이 dp [i][j]가 되고

아닐 떼 셋 중 가장 작은값+1을 해주면 된다.

 

이걸 이제 구현만 해주면 끝.

생각보다 간단하다.

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
a,b=map(int,input().split())
l=[]
for i in range(a):
    rty=list(input().strip())
    for g in range(b):
        rty[g]=int(rty[g])
    l.append(rty)
dp=[[-1 for i in range(b+1)]for g in range(a+1)]
ans=[[0 for i in range(b+1)]for g in range(a+1)]
def f(i,j):
    if dp[i][j]!=-1:return dp[i][j]
    if i==0 or j==0:
        dp[i][j]=l[i][j]
        ans[i][j]=max(ans[i][j],dp[i][j])
        return dp[i][j]
    fr=f(i-1,j)
    se=f(i,j-1)
    th=f(i-1,j-1)
    if fr==se==th and l[i][j]==1:
        dp[i][j]=fr+1
        ans[i][j]=max(ans[i][j],dp[i][j])
        return dp[i][j]
    else:
        if l[i][j]==1:
            dp[i][j]=min([fr,se,th])+1
        else:
            dp[i][j]=0
        ans[i][j]=max([ans[i][j],ans[i-1][j],ans[i][j-1],ans[i-1][j-1]])
        return dp[i][j]
f(a-1,b-1)
#print(dp)
print(ans[a-1][b-1]**2)