[BOJ] 1915

less than 1 minute read

가장 큰 정사각형

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

점화식만 알고 난다면 쉽게 풀리는 문제였습니다.
dp[i][j]map[i][j] 를 오른쪽 아래 꼭짓점으로 하는 정사각형의 최대 변의 길이라고 할 때
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1 의 점화식을 이용하면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1915.cpp

Categories:

Updated:

Leave a comment