# 1915. 가장 큰 정사각형 [링크](https://www.acmicpc.net/problem/1915) | 난이도 | 정답률(\_%) | | :----: | :---------: | |Silver I|28.739| ## 설계 ### 메모이제이션 map[y][x]가 정사각형인 경우 (==1) 현재 위치 (y,x)에서 가질수 있는 최대 정사각형의 길이는 memo[y][x] = min(memo[y-1][x-1], memo[y-1][x], memo[y][x-1]) + 1 이다. (c에서 min에 인자 3개들어가면 오류인것에 유의) ## 정리 | 내 코드 (ms) | 빠른 코드 (ms) | | :----------: | :------------: | |12| | ## 고생한 점 map의 시작 index를 1부터 잡았으나, 한 줄 씩 읽은 line을 map으로 변환할 때 0부터 index를 잡아 오류가 발생함 ## code ```cpp #include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; int memo[1001][1001] = { 0, }; void solution() { int N, M; cin >> N >> M; for (int i = 1; i <= N; i++) { string line; cin >> line; for (int j = 1; j <= M; j++) { memo[i][j] = line[j - 1] - '0'; } } int answer = 0; for (int y = 1; y <= N; y++) { for (int x = 1; x <= M; x++) { if (memo[y][x] != 1) { continue; } int left, up, leftup; left = memo[y][x - 1]; up = memo[y - 1][x]; leftup = memo[y - 1][x - 1]; memo[y][x] = min(min(left, up), leftup) + 1; answer = max(memo[y][x], answer); } } cout << answer * answer << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solution(); return 0; } ```
Activity