[BOJ] 1915. 가장 큰 정사각형(Python) / DP

1915번: 가장 큰 정사각형

 

문제 보자마자 바로 반복문으로 풀었는데, 어쩐지 쉽다 했더니 바로 시간초과;

아니나 다를까 Dynamic Programming 문제이다. 골드 5 문제이기도 하고.

요새 계속 기초 DP 문제를 풀고 있는데, 여전히 발상 자체가 어려운 것 같다.

DP는 사실 코드는 짧은데, 이를 생각해내기가 참 어렵다ㅠㅠ 아직 DP초보라,, 더 노력하는 수밖에!

결국 다른 분 코드를 참고해서 풀었다.

cagongman.tistory.com/18

[백준][Python] 1915 가장 큰 정사각형 - 풀이 공유

이 문제는 DP 문제 중에서도 쉬운 편에 속한다고 한다.

보자마자 아! 싶었다.. 이해했다. 코드를 잘 짜시는 분인 것 같다. 

 

• 현 위치가 1인 경우 좌상, 상, 좌 부분을 확인해 가장 작은 값에 +1 해주어 가능한 변의 길이를 표시한다. (핵심 포인트!)
  • dp[i][j]에 A[i-1][j-1]을 정사각형의 우측하단 꼭짓점으로 하여 만들 수 있는 정사각형 변의 길이를 저장
• 이 때, 최대 변의 길이를 갱신한다. 

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = []
for i in range(N):
    s = input()
    A.append(list(map(int, list(s))))

# A 탐색하면서 채울 DP 테이블
dp = [[0] * (M+1) for _ in range(N+1)]
size = 0    # 최대 변의 길이

for i in range(1, N+1):
    for j in range(1, M+1):
        if A[i-1][j-1]:
            dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
            size = max(size, dp[i][j])
print(size ** 2)

 

* 고찰 : DP 연습 많이 하자.. 아직 한참 부족한 것 같다.