문제접근
•
dp에 무엇을 담을까 고민을 함
그 위치에서 최대로 만들 수 있는 정사각형의 한변의 길이를 담으면 되겠다 판단
예를들어, dp[2][2](a지점)에 들어가게 될 녀석들을 생각해보면
0인 부분엔 그릴 수 없기 때문에 위와 같이 두가지의 경우가 나옴
따라서 dp[2][2](a지점)엔 1이 들어가게 됨
→ 현재 위의 그림은 dp에 관련된 행렬이 아니라 처음에 입력 받은값에 관련된 행렬이기 때문에 주의
dp행렬은 밑에서 그릴 예정
•
점화식 찾기
<input행렬>
우리가 a를 기준으로 최대정사각형을 만든다고 했을때 우리는 b c d 에도 그릴 수 있는지, 즉 0이 아닌지(사각형을 그릴 수 없는지)를 판단해줘야함
위의 방식으로 dp행렬을 만들어보면
<dp행렬>
이런 형태가 나오게 되고, 빨간부분 과 파란부분 을 봐야함
1.
빨간부분
•
좌측,좌대각선,위가 모두 1(사각형을 그릴 수 있는 상태)
2.
파란부분
•
좌측,좌대각선,위 모두 사각형을 그릴 수 있는 상태
•
input을 보면 그 지점 자체가 0으로 사각형을 그릴 수 없기 때문에 dp[3][4](파란원)은 0
좌측, 좌대각선, 위 중 하나라도 사각형을 그릴 수 없으면 정사각형을 완성시킬 수 없기 때문에 셋 중에서 최솟값에 +1이 되는 형태
•
고려한점
1.
<dp행렬>
파란 부분의 경우 점화식대로 풀 수가 없기 때문에(좌측, 좌대각선, 위가 존재하지 않음) input을 그대로 적어놓으면 됨
결과적으로 파란색 이외의 부분만 구하면 됨
2.
입력
string으로 입력 받고 한글자씩 int로 변환하여 넣어줌
//pseudo code
vector<vector<int> > dp
int n,m
cin >> n,m
cin >> dp
while //n+1행부터
while //m+1열부터
C++
복사
놓쳤던 부분
1.
최대 길이를 구하는 것이 아니라 최대 넓이를 구하는 것
최대 길이를 구했기 때문에 제곱하면 됨
2.
최대 길이를 구하는 조건
if (i == 0 || j == 0)
{
max = std::max(dp[i][j], max);
continue ;
}
C++
복사
나의 코드에서는 [1][어디든] [어디든][1] 은 입력 받은 결과 그대로를 쓰기 때문에 저 인덱스들에 대해서는 max값이 업데이트가 되지 않음
예를들어
0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Plain Text
복사
에서 1을 업데이트 하지 못하고 max = 0이 되어 버리기 때문에 조건을 추가해야함
코드
5996 KB
12 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int n,m;
std::vector<std::vector<int> > dp;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int i;
int j;
std::string input_arr;
i = 0;
std::cin >> n >> m;
dp.resize(n + 1, std::vector<int>(m + 1));
while (++i <= n)
{
j = 0;
std::cin >> input_arr;
while (++j <= m)
dp[i][j] = input_arr[j - 1] - '0';
}
}
void solution()
{
int i;
int j;
int max;
i = 0;
max = 0;
while (++i <= n)
{
j = 0;
while (++j <= m)
{
if (dp[i][j] == 0)
continue ;
if (i == 0 || j == 0)
{
max = std::max(dp[i][j], max);
continue ;
}
dp[i][j] = std::min(std::min(dp[i][j - 1], dp[i - 1][j - 1]), dp[i - 1][j]) + 1;
max = std::max(dp[i][j], max);
}
}
std::cout << max * max;
}
int main(void)
{
input_setting();
input();
solution();
return (0);
}
C++
복사
