[dp/백준] 1915번: 가장 큰 정사각형

-문제: https://www.acmicpc.net/problem/1915

 

-정답 풀이:

값 입력 받을 때 주의하기 

띄어쓰기 없이 주어지고, 모양이 0100이므로 이진수로 읽힐 수 있어서 이를 list로 받아야한다 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
data = []
dp = [[0] * m for _ in range(n)]

for _ in range(n):
    data.append(list(map(int,list(input().rstrip())))) # 여기 split아님. 주의하기
    
answer = 0
for i in range(n):
    for j in range(m):
        if i == 0 or j == 0:
            dp[i][j] = data[i][j]
        elif data[i][j] == 0:
            dp[i][j] = 0
        else: 
            dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
        answer = max(dp[i][j],answer)
        
print(answer ** 2)

 

-시도해본 풀이(틀림)

주변 값 중 최댓값을 사용해야한다고 생각했음. 

그리고 특정 위치 주변의 값들이 모두 같고, 0이 아닌 경우에 정사각형이 성립된다고 생각함. 

n,m=map(int,input().split())
dp=[]
for _ in range(n):
    dp.append(list(map(int,list(input().rstrip()))))
for i in range(1,n):
    for j in range(1,m):
        if dp[i][j]!=0 and dp[i-1][j-1]!=0:
            if dp[i-1][j]==dp[i][j-1] and dp[i][j-1]==dp[i-1][j-1]:
                dp[i][j]+=dp[i-1][j-1]
            else:
            #이 경우에 대해서는 생각 안하는 것 같기도
                dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
             
for i in range(n):
    answer=max(dp[i])
print(answer**2)