[백준/JAVA] 1915번: 가장 큰 정사각형

🔺 문제

1915번: 가장 큰 정사각형

 

 

🔺 코드

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();
    }
}

✅ 해결 아이디어
✔ DP - 점화식
- DP[ i ][ j ] : i,j의 위치를 오른쪽 아래 꼭짓점으로 정하고, 해당 자리에서 그릴 수 있는 최대 정사각형의 변의 길이

 

---

🔺 다른 풀이들

[BOJ] 백준 1915번 : 가장 큰 정사각형 (JAVA)

[BOJ 백준] 가장 큰 정사각형 (1915) Java

---

💬 느낀 점

2차원 배열 DP... 배열 의미를 정의하는거부터 쉽지 않구만...

 

 

1회독	2회독	3회독	4회독	5회독
V	7/7

 

 

(+7/7 2회독)

맙소사... 변한 부분이라고는 입력 받는 부분 조금 다를 뿐인데...

메모리랑 시간 차이가 이렇게 날수가... ㄴㅇㄱ

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);
    }
}
 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편