-
[백준 - 1915번] 가장 큰 정사각형 - Java //Wello Horld//Algorithm/BOJ(Baekjoon Online Judge) 2019. 7. 25. 13:17
이번에는 BOJ의 1915번 문제 "가장 큰 정사각형"을 풀어보도록 하자
다이나믹 프로그래밍으로 풀면 간단하게 풀리는 문제이다. 입력으로 먼저 n, m 주어지고, 그 다음 n개의 줄에 m개 만큼 "0"이나 "1"이 주어진다. 이것을 이용해서, 1로 이루어져 있는 가장 큰 정사각형의 넓이를 구하면 되는 문제이다. 예제를 보면
- 4 4
- 0100
- 0111
- 1110
- 0010
이 주어졌을 때, 가운데에 있는 굵은 글씨부분이 가장 큰 정사각형이고, 그 넓이는 4가 된다.
이것을 풀 때, 입력을 배열로 받으면서 계산까지 가능하도록 프로그램을 만들어서, 살짝 더럽긴하지만, 성공한 코드는 아래와같다.
import java.io.*; import java.util.*; public class sample { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[][] dp = new int[1001][10001]; int ans = 0; for(int i = 0; i < n; i ++){ char[] line = br.readLine().toCharArray(); for(int j = 0; j < line.length; j++){ //dp의 0행, 0열 -> 모두 '0'으로 만들어주기 위해 dp[i+1][j+1] 로 해줌 dp[i + 1][j + 1] = line[j] - '0'; if(dp[i + 1][j + 1] != 0){ int temp = Math.min(dp[i][j], dp[i][j + 1]); dp[i + 1][j + 1] = Math.min(temp, dp[i + 1][j]) + 1; ans = Math.max(ans, dp[i + 1][j + 1]); } } } bw.write((ans * ans) + "\n"); bw.flush(); br.close(); bw.close(); } }
문제 : https://www.acmicpc.net/problem/1915
'Algorithm > BOJ(Baekjoon Online Judge)' 카테고리의 다른 글
[백준 - 15904번] UCPC는 무엇의 약자일까? - Java //Wello Horld// (0) 2019.07.25 [백준 - 2166번] 다각형의 면적 - Java //Wello Horld// (0) 2019.07.25 [백준 - 1016번] 제곱 ㄴㄴ수 - Java //Wello Horld// (0) 2019.07.23 [백준 - 1717번] 집합의 표현 - Java //Wello Horld// (0) 2019.07.23 [백준 - 11051번] 이항계수2 - Java //Wello Horld// (0) 2019.07.23