혼종 꼬지마루
[백준] 4095 - 최대 정사각형 본문
말 그대로 최대 정사각형의 크기를 구하는 문제
주어진 map에서 최대로 정사각형이 되는 크기의 너비나 높이를 구하면 됨
1. map을 순회하면서 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]의 최소 값을 구한다
- 이유는 저 3개의 포인트는 각각 정사각형의 크기를 가진 값을 저장하기 때문
- 하나라도 작으면 작은 사이즈의 정사각형을 넣어 주어야 하기 때문이다.
ex) 0 1 1 0 0 0 1 1 0 0
0 1 1 1 0 ----->>>>> 0 1 4 1 0
0 1 1 1 0 0 1 4 4 0
0 1 1 1 0 0 1 4 9 0
2. 최소값의 너비나 높이를 구하기 위해 sqrt해주고, +1해 준 뒤 다시 제곱하여 dp[i][j]에 넣어준다.
3. 시간 복잡도는 O(N^2)이 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <iostream> #include <cmath> #define MAXSIZE 1002 #define MIN(X, Y) ((X) > (Y) ? (Y) : (X)) using namespace std; int map[MAXSIZE][MAXSIZE] = { 0 }; long long dp[MAXSIZE][MAXSIZE] = { 0 }; int main(void) { while (1) { int N, M, dab = 0; cin >> N >> M; if (N == 0 && M == 0) break; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) { cin >> map[i][j]; dp[i][j] = 0; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (map[i][j] == 1) { long long size = MIN(dp[i - 1][j - 1], MIN(dp[i][j - 1], dp[i - 1][j])); if (!size) dp[i][j] = 1; else { size = sqrt(size) + 1; dp[i][j] = size * size; } } else dp[i][j] = 0; dab = dab > dp[i][j] ? dab : dp[i][j]; } } cout << sqrt(dab) << endl; } return 0; } | cs |
'Algorithms > DP' 카테고리의 다른 글
[백준] 1103 - 게임 (0) | 2019.10.13 |
---|---|
[백준] 17070 - 파이프 옮기기 (0) | 2019.10.13 |
[백준] 15559 - 내 선물을 받아줘 (0) | 2019.04.13 |
[백준] 1520 - 내리막길 (0) | 2018.09.14 |
[백준] 9465 - 스티커 (0) | 2018.09.08 |