-
[백준] #19115 가장 큰 정사각형 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 17:37
문제
https://www.acmicpc.net/problem/1915
목표
0과 1로 이루어진 배열이 주어질때 1로 이루어진 가장 큰 정사각형의 넓이를 출력
풀이
dp를 사용하여 dp배열에 가장 큰 정사각형의 변의 길이를 저장한다.
점화식
dp[i][j] =
if ( dp[i][j]==1 && dp[i][j-1]!=0 && dp[i-1][j]!=0 && dp[i-1][j-1]!=0 )
dp[i][j] = min(dp[i][j-1], dp[i-1][j]);
dp[i][j] = min(dp[i][j], dp[i-1][j-1]) + 1;
즉, 왼쪽, 위쪽, 왼쪽위쪽의 배열값이 1이 아니라면, 3방향의 값중 최소값에 1을 더해진 값이 현재 dp배열값이된다.
코드
#include <iostream> #define MAX 1001 using namespace std; int N, M; int dp[MAX][MAX]; int func() { int res = 0; for (int i=1; i<=N; ++i) { for (int j=1; j<=M; ++j) { if (dp[i-1][j]!=0 && dp[i][j-1]!=0 && dp[i-1][j-1]!=0 && dp[i][j]==1) { dp[i][j] = min(dp[i-1][j], dp[i][j-1]); dp[i][j] = min(dp[i-1][j-1], dp[i][j]) + 1; } if (res < dp[i][j]) res = dp[i][j]; } } return res * res; } int main() { cin >> N >> M; for (int i=1; i<=N; ++i) { for (int j=1; j<=M; ++j) { scanf("%1d", &dp[i][j]); } } cout << func(); }
'Algorithm > 알고리즘 백준 풀이' 카테고리의 다른 글
[백준] #14003 가장 긴 증가하는 부분수열5 - (DP) (0) 2020.03.02 [백준] #11049 행렬 곱셈 순서 - (DP) (0) 2020.03.02 [백준] #9252 LCS2(Longest Common Subsequence) - (DP) (0) 2020.03.02 [백준] #11659 구간합 구하기4 - (DP) (0) 2020.03.02 [백준] #2579 계단 오르기 - (DP) (0) 2020.03.02