코테/백준
[백준/JAVA] 1915번: 가장 큰 정사각형
imname1am
2023. 5. 16. 16:36
반응형
🔺 문제
1915번: 가장 큰 정사각형
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
www.acmicpc.net
🔺 코드
|
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
38
39
40
41
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
long max = 0;
// DP 배열 초기화
long[][] DP = new long[1001][1001];
for(int i = 1 ; i <= n ; i++) {
String[] str = br.readLine().split("");
for(int j = 1 ; j <= m ; j++) {
DP[i][j] = Long.parseLong(str[j - 1]);
}
}
// 점화식 이용해 배열 채우기
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= m ; j++) {
// 현재 자리의 원래 값이 1이라면,
// 이 위치의 위.왼.대각선 왼쪽 위 값 中 가장 작은 값 + 1
if(DP[i][j] == 1 && i > 0 && j > 0) {
DP[i][j] = Math.min(Math.min(DP[i - 1][j - 1], DP[i][j - 1]), DP[i - 1][j]) + 1;
}
// 최댓값 업데이트
if(max < DP[i][j]) {
max = DP[i][j];
}
}
}
System.out.println(max * max);
br.close();
}
}
|
cs |
✅ 해결 아이디어
✔ DP - 점화식
- DP[ i ][ j ] : i,j의 위치를 오른쪽 아래 꼭짓점으로 정하고, 해당 자리에서 그릴 수 있는 최대 정사각형의 변의 길이
🔺 다른 풀이들
[BOJ] 백준 1915번 : 가장 큰 정사각형 (JAVA)
문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 입력 첫째
steady-coding.tistory.com
[BOJ 백준] 가장 큰 정사각형 (1915) Java
링크 : https://www.acmicpc.net/problem/1915 문제 설명 : 더보기 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와
subbak2.com
💬 느낀 점
2차원 배열 DP... 배열 의미를 정의하는거부터 쉽지 않구만...
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 7/7 |
(+7/7 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
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
long[][] dp = new long[n][m];
for(int i = 0 ; i < n ; i++) {
char[] ch = br.readLine().toCharArray();
for(int j = 0 ; j < m ; j++) {
dp[i][j] = ch[j] - '0';
}
}
long max = 0;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(dp[i][j] == 1 && i > 0 && j > 0) {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + dp[i][j];
}
if(max < dp[i][j]) {
max = dp[i][j];
}
}
}
System.out.println(max * max);
}
}
|
cs |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편
반응형