Memo
•
접근 방법
이차원 배열에 값을 저장해 놓습니다. 가로 세로 길이를 1씩 증가시킨 상태여야 하는데 그 이유는 코드의 일관성 때문입니다. 처음에 배열을 0으로 초기화 합니다. 그 후에 1,1 부터 N,N 까지 input을 받습니다.
1,1 부터 N,N 까지 각 행마다 각 열을 순회하는데, 현재 자신의 위치의 값이 0이라면 정사각형은 절때 만들어 질 수 없기 때문에 그 곳은 분기를 통해 지나치고, 현재 자신의 위치의 값이 1이라면 위, 왼쪽 위 대각선, 왼쪽을 검사하여 가장 작은 값에 1을 더한 값 을 저장합니다.
가장 작은 값을 선택하는 이유는, 현재 그 자리에 그 값이 왜 있는지를 생각해 보면 되는데, 조사하려고 하는 그 자리에 있는 값은 0을 만났을 때를 제외한 자신이 만들수 있는 가장 긴 길이의 정사각형 한 변이기 때문입니다. 따라서 그 변은 확정적으로 자신의 현재 위치에서 만들 수 있는 것입니다.
가장 긴 변을 순회하면서 계속해서 업데이트를 해나가면서, 최종적으로 가장 큰 정사각형의 넓이를 구해낼 수 있습니다.
Code
제출 날짜
@2/24/2021
메모리
5996 KB
시간
12 ms
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::vector<int> > sq;
size_t n, m;
int g_max;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::string tmp;
std::cin >> n >> m;
sq.resize(n + 1, std::vector<int>(m+1));
for (size_t i = 1 ; i < n + 1 ; i++)
{
std::cin >> tmp;
for (size_t j = 1 ; j < tmp.size() + 1 ; j++)
sq[i][j] = tmp[j - 1] - '0';
}
g_max = 0;
}
void logic()
{
for (size_t i = 1; i < n + 1 ; i++)
for (size_t j = 1 ; j < m + 1 ; j++)
{
if (!sq[i][j])
continue;
sq[i][j] = std::min({sq[i - 1][j], sq[i][j - 1], sq[i - 1][j - 1]}) + 1;
g_max = g_max > sq[i][j] ? g_max : sq[i][j];
}
}
void solve()
{
logic();
std::cout << g_max * g_max;
}
int main()
{
input();
solve();
return (0);
}
C++
복사
(+ 추가적으로)
맞은 사람 코드중에서 4ms가 있어서 봤는데, 좀 놀라웠습니다.
A, B 변수가 있는데 각각 0, 1 로 초기화 되어있고 그 값은 swap을 통해 계속해서 바뀌어 가고 있었습니다.
@suhshin 덕분에 코드를 빠르게 파악했는데, 배열의 크기를 n x m 으로 두지 않고, 2 x m으로 두고나서 인풋을 받음과 동시에 누적합을 계산했습니다...
아래 코드는 위 로직을 가지고 작성한 코드입니다.
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::vector<int> > sq;
size_t n, m;
int g_max;
int A, B;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void logic()
{
input_faster();
std::string tmp;
std::cin >> n >> m;
sq.resize(2, std::vector<int>(m+1));
A = 0;
B = 1;
int val_tmp;
g_max = 0;
for (size_t i = 1 ; i < n + 1 ; i++)
{
std::cin >> tmp;
for (size_t j = 1 ; j < tmp.size() + 1 ; j++)
{
if (tmp[j - 1] == '0')
sq[B][j] = tmp[j - 1] - '0';
else
{
sq[B][j] = std::min({sq[A][j], sq[B][j - 1], sq[A][j - 1]}) + 1;
g_max = g_max > sq[B][j] ? g_max : sq[B][j];
}
}
val_tmp = A;
A = B;
B = val_tmp;
}
}
void solve()
{
logic();
std::cout << g_max * g_max;
}
int main()
{
solve();
return (0);
}
C++
복사
위 코드의 결과는
처음 작성한 코드의 메모리와 시간에 비해서 월등하게 좋아졌습니다.
