Search

가장 큰 정사각형

Created
2021/03/23 01:58
문제 번호
1915
카테고리
DP

Memo

BSQ 때 진행했던 문제와 동일
MapMemoization 벡터를 따로 둘 필요 없이 Map 벡터에 입력을 받으면 바로 MemoizationMap 위에 수행하면 됨
주의할 점은 입력을 받을 때 공백 문자를 없이 받기 때문에 문자열로 입력을 받아 파싱해줘야 함
(x,y)(x, y)에 해당 좌표에서 만들 수 있는 가장 큰 정사각형 길이를 누적 받아가면 되는데, 이 때 비교 대상은 총 3개 → (x1,y)(x - 1, y) (x,y1)(x, y- 1), (x1,y1)(x - 1, y - 1)
1.
정사각형이 아니라면 위 점들은 0을 갖고 있기 때문에 (x,y)(x, y)에는 자기 자신인 11짜리 정사각형이 됨
2.
정사각형이라면 위 점들도 각 점에서 만들 수 있는 최대 정사각형 길이를 갖고 있을 것이기 때문에, 3개의 점 중에서 최소 값이, (x,y)(x, y)에서 이룰 수 있는 정사각형이 됨 (마찬가지로 자기 자신 길이 11을 더해줘야 함)
nn, mm이었다면, n×mn \times m의 반복 횟수안에 3개의 점에 대한 비교 구문만으로 정사각형 누적 최대 길이를 구해나갈 수 있음
Loop에서 비교 구문은 값이 00이 아닐 때만 수행하면 됨 → 비교 후 +1+1을 해주는 구문이 00일 때도 수행되면, 결과보다 더 큰 값을 누적 받아오므로 정사각형으로 추정할 수 있는 값에 대해서만 수행해야 함

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++