백준 알고리즘 풀이 1915번 - 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

 

1915번

- 다이나믹 프로그래밍

 

- 알고리즘 -

1. 전체 맵의 오른쪽 아래를 기준으로 정사각형의 왼쪽 위라고 가정한다.

2. counts[][] 배열을 만들어서 그 지점을 좌측 상단으로 하는 가장 큰 정사각형이라고 정의한다.

3. counts[a][b] = min(counts[a+1][b],counts[a][b+1],counts[a+1][b+1])+1

-시간 복잡도-

맵의 총크기 : O(n) * O(n)

각 경우당 4번씩 탐색. 따라서 총 시간 복잡도 = 4 * O(n) * O(n)

- 예외 조건 -

1. counts[a][b]에서 a==dimY 이나 b==dimX 라면 counts[a][b]=1.

 

dp라고 인식하고, counts[a][b] = min(counts[a+1][b],counts[a][b+1],counts[a+1][b+1])+1 이 부분을 생각하는 것이 조금 복잡했다. 저것만 생각할 수 있다면 어렵지 않게 풀 수 있던 문제. 

-소스 코드-

#include <iostream>
#include <cstring>

using namespace std;

int map[1001][1001];
int counts[1001][1001]={0,};
int dimX,dimY;

int main()
{
	int ans=0;
	cin>>dimY>>dimX;
	for(int i=1;i<=dimY;i++){
		for(int j=1;j<=dimX;j++){
			scanf("%1d",&map[i][j]);
		}
	}
	for(int y=dimY;y>=1;y--){
		for(int x=dimX;x>=1;x--){
			if(map[y][x]==1){
				int minimum=1001;
				if(x==dimX || y==dimY){
					minimum=0;
				}
				else{
					for(int i=0;i<=1;i++){
						for(int j=0;j<=1;j++){
							if(i==0 && j==0) continue;
							if(minimum>counts[y+i][x+j]) minimum=counts[y+i][x+j];
						}
					}
				}
				counts[y][x]=minimum+1;
				if(minimum>=ans) ans=minimum+1;
			}
		}
	}
	cout<<ans*ans;
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)