c++, python 백준_1915_"가장 큰 정사각형"

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

1915번: 가장 큰 정사각형

 

 

​

DP를 이용해 해결했다.

​

1,1 부터 시작해서

만약 그 자리가 '1'이라면

[i-1][j-1] , [i-1][j] , [i][j-1] 중에 가장 작은 것 + 1 을

그 자리에 넣어주었다.

​

그렇게 하면 아래로 내려가면서

정사각형이니까 최대 한쪽 면의 수가 나온다.

​

답으로 그 수를 제곱하였다.

​

c++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main(void) {

	int n, m;
	cin >> n >> m;

	vector<vector<int>> board(n+1, vector<int>(m+1,0));
	
	for (int i = 1; i <= n; i++) {
		string temp;
		cin >> temp;

		for (int j = 1; j <= m; j++) {
			board[i][j] = temp[j-1] - '0';
		}
	}

	int ans = 0;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (board[i][j]) {
				int mini = min(board[i - 1][j - 1], min(board[i - 1][j], board[i][j - 1]));

				board[i][j] = mini + 1;

				if (ans < board[i][j])
					ans = board[i][j];
			}
		}
	}
	
	cout << ans * ans;
}

 

python

n,m = map(int,input().split())

board = [[0 for i in range(m+1)]]

for i in range(n):
    board.append([0] + list(input().strip()))

dp = [[0] * (m + 1) for i in range(n + 1)]

ans = 0

for i in range(1,n+1):
    for j in range(1,m+1):
        if board[i][j] == '1':
            mini = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))

            dp[i][j] = mini + 1

            if ans < dp[i][j] :
                ans = dp[i][j]

print(ans**2)