1915번: 가장 큰 정사각형

Memo

이번 문제는 42 피씬과정에서 있었던 BSQ 과제의 알고리즘과 똑같았다.

크게 어려운 부분은 없었지만 입력이 숫자로 들어오는게 아니라 문자 배열로 들어오는 것을 고려했어야 했다.

그래서 string을 입력받고 인덱스 접근을 통해서 벡터에 넣어주었다.

• 인풋을 받으면서 동시에 dp를 적용하면 시간에 차이가 있을 줄 알고 시도해 보았으나 출력시간에 차이가 없었다. 아마 O(N * M) 과 O( 2 * N * M) 이라서 크게 차이가 나지 않았던 것 같다.
• 코드를 다 풀고 채점 현황을 보다가 메모리와 시간이 엄청 적게 나오는 코드가 있었다. 너무 신기하기도 하고 생각이 너무 참신해서 해당 내용도 아래에 구현해 두었다.

Code (기존 방법)

제출 날짜

2021/02/24

메모리

5996 KB

시간

12 ms

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int N;
int M;
int result;
std::vector<std::vector<int> > map;

void output()
{
	std::cout << result * result;
}

void solution()
{
	for (int i = 1 ; i <= N ; i++)
		for (int j = 1 ; j <= M ; j++)
		{
			if(map[i][j] == 1)
				map[i][j] += std::min({map[i - 1][j], map[i - 1][j - 1], map[i][j - 1]});
			result = std::max(result, map[i][j]);
		}
}

void input()
{
	std::string str;

	std::cin >> N >> M;
	map = std::vector(N + 1, std::vector(M + 1, 0));
	for (int i = 1 ; i <= N ; i++)
	{
		std::cin >> str;
		for (int j = 1 ; j <= M ; j++)
			map[i][j] = str[j - 1] - '0';
	}
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	solution();
	output();
}

Code (새로운 방법)

제출 날짜

2021/02/24

메모리

2152 KB

시간

8 ms

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int N;
int M;
int result;
std::vector<std::vector<int> > map;

void output()
{
	std::cout << result * result;
}

void solution()
{
	std::string str;
	int A = 0;
	int B = 1;
	std::cin >> N >> M;
	map = std::vector(2, std::vector(M + 1, 0));

	for (int i = 1 ; i <= N ; i++)
	{
		std::cin >> str;
		for (int j = 1 ; j <= M ; j++)
		{
			if(str[j - 1] == '0')
				map[B][j] = 0;
			else
			{
				map[B][j] = std::min({map[A][j], map[B][j - 1], map[A][j - 1]}) + 1;
				result = std::max(result, map[B][j]);
			}
		}
		std::swap(A, B);
	}
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	solution();
	output();
}