Memo
BSQ 때 진행했던 문제와 동일
Map과 Memoization 벡터를 따로 둘 필요 없이 Map 벡터에 입력을 받으면 바로 Memoization을 Map 위에 수행하면 됨
주의할 점은 입력을 받을 때 공백 문자를 없이 받기 때문에 문자열로 입력을 받아 파싱해줘야 함
에 해당 좌표에서 만들 수 있는 가장 큰 정사각형 길이를 누적 받아가면 되는데, 이 때 비교 대상은 총 3개 → ,
1.
정사각형이 아니라면 위 점들은 0을 갖고 있기 때문에 에는 자기 자신인 짜리 정사각형이 됨
2.
정사각형이라면 위 점들도 각 점에서 만들 수 있는 최대 정사각형 길이를 갖고 있을 것이기 때문에, 3개의 점 중에서 최소 값이, 에서 이룰 수 있는 정사각형이 됨 (마찬가지로 자기 자신 길이 을 더해줘야 함)
행이 , 열이 이었다면, 의 반복 횟수안에 3개의 점에 대한 비교 구문만으로 정사각형 누적 최대 길이를 구해나갈 수 있음
각 Loop에서 비교 구문은 값이 이 아닐 때만 수행하면 됨 → 비교 후 을 해주는 구문이 일 때도 수행되면, 결과보다 더 큰 값을 누적 받아오므로 정사각형으로 추정할 수 있는 값에 대해서만 수행해야 함
Code
제출 날짜
@2/24/2021
메모리
5996 KB
시간
8 ms
#include <algorithm>
#include <iostream>
#include <vector>
int g_row;
int g_col;
int g_max;
std::vector<std::vector<int>> g_map;
void pre_setting(void)
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
void input_action(void)
{
std::cin >> g_row >> g_col;
g_map = std::vector<std::vector<int>>(g_row + 1, std::vector<int>(g_col + 1, 0));
for (int i = 1; i <= g_row; i++)
{
std::string tmp(g_col, '\0');
std::cin >> tmp;
for (int j = 0; j < g_col; j++)
g_map[i][j + 1] = tmp[j] - '0';
}
}
void logic(void)
{
for (int i = 1; i <= g_row; i++)
{
for (int j = 1; j <= g_col; j++)
{
if (g_map[i][j])
{
g_map[i][j] =
std::min({ g_map[i - 1][j], g_map[i][j - 1], g_map[i - 1][j - 1] }) + 1;
g_max = std::max(g_max, g_map[i][j]);
}
}
}
}
void output_action(void)
{
std::cout << g_max * g_max;
}
void solution(void)
{
input_action();
logic();
output_action();
}
int main(void)
{
pre_setting();
solution();
return (0);
}
C++
복사