1915번: 가장 큰 정사각형
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
www.acmicpc.net
이런식으로 배열이 주어지면 1로만 이루어진 가장 큰 정사각형의 넓이를 구하는 문제입니다.
우선 2 * 2의 정사각형의 예로 들면
여기서 맨 오른쪽 아래(2, 2)를 기준으로 왼쪽(2, 1), 위(1, 2), 왼쪽 위(1, 1)의 수가 모두 1이기때문에 정사각형이 됩니다.
여기서 dp[i][j]의 값은 dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]의 값들로 인해 결정이 되는것을 알 수 있습니다.
위의 그림은 dp[i - 1][j - 1]이 0이므로 정사각형이 아닙니다.
여기서 도출되는 점화식은 dp[i][j] += min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])입니다.
이 점화식은 현재 좌표의 값이 1일 경우에만 적용됩니다. (0일 경우에는 그냥 넘겨줍니다)
계산 과정에서 ans를 계속 갱신시켜줘서 마지막에 넓이를 출력해주시면 됩니다.
[C++]
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][1001];
int N, M, ans;
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
char ch;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> ch;
dp[i][j] = ch - '0';
if (dp[i][j]) dp[i][j] += min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
ans = max(ans, dp[i][j]);
}
}
cout << ans * ans << '\n';
return 0;
}
|
cs |
[Java]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int dp[][] = new int[1001][1001];
static int N, M, ans;
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
char ch[] = st.nextToken().toCharArray();
for (int j = 1; j <= M; j++) {
dp[i][j] = ch[j - 1] - '0';
if (dp[i][j] == 1) {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
ans = Math.max(ans, dp[i][j]);
}
}
}
}
public static void main(String[] args) throws Exception {
input();
System.out.println(ans * ans);
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 2616 소형기관차 (0) | 2021.02.27 |
|---|---|
| boj 11049 행렬 곱셈 순서 (0) | 2021.02.20 |
| boj 1912 연속합 (0) | 2021.02.18 |
| boj 10211 Maximum Subarray (0) | 2021.02.18 |
| boj 10826 피보나치 수 4 (0) | 2021.02.08 |