회고
- 전형적인 dp 문제
- dp[i][j] = Min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- 규칙을 찾는것이 쉽지 않다.
- 차근차근.. 하나씩 뜯어보자.
풀이
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 |
위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.
입력
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
출력
첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.
예제 입력 1
4 4 0100 0111 1110 0010 |
예제 출력 1
4 |
소스
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static int N; public static int M; public static char[][] map; public static int[][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); map = new char[N][M]; dp = new int[N][M]; for (int i = 0; i < N; i++) { map[i] = br.readLine().toCharArray(); } int max = Integer.MIN_VALUE; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int min = Integer.MAX_VALUE; if (map[i][j] == '1') { // 왼쪽, 위, 왼쪽위 if (0 <= j - 1 && 0 <= i - 1) { min = Math.min(min, dp[i][j - 1]); min = Math.min(min, dp[i - 1][j]); min = Math.min(min, dp[i - 1][j - 1]); } if (min == Integer.MAX_VALUE) { dp[i][j] = 1; } else { dp[i][j] = min + 1; } max = Math.max(max, dp[i][j]); } } } System.out.println(max * max); br.close(); }}
'스터디 > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 11053] 가장 긴 증가하는 부분 수열 (LIS) (0) | 2018.12.03 |
|---|---|
| [백준 1600] 말이 되고픈 원숭이 (0) | 2018.11.26 |
| [백준 2098] 외판원 순회 (0) | 2018.11.26 |
| [백준 9376] 탈옥 (0) | 2018.11.26 |
| [백준 14500] 테트로미노 (0) | 2018.11.26 |