https://www.acmicpc.net/problem/1915
< dp 알고리즘 >
- 동적 계획법 (Dynamic Programming)
- 복잡한 문제를 여러 개의 간단한 문제로 나눠서 푼다.
num이나 dp 배열의 크기를 n, m으로 설정하면, n 또는 m이 1로 들어왔을 때 i-1 또는 j-1 인덱스가 없어서 indexError가 생긴다.
그러므로 n+1, m+1로 크기를 설정하고, for 반복문을 i=1, j=1 부터 시작한다.
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 | import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int i, j, max=0; int n = sc.nextInt(); int m = sc.nextInt(); String[] num = new String[n+1]; int[][] dp = new int[n+1][m+1]; for(i=1; i<n+1; i++) { num[i] = sc.next(); for (j = 1; j < m+1; j++) { dp[i][j] = num[i].charAt(j-1)-'0'; } } for (i=1; i < n+1; i++) { for (j = 1; j < m+1; j++) { if (dp[i][j] == 1) { dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1; max = dp[i][j]<max ?max :dp[i][j]; } } } System.out.println(max*max); sc.close(); } private static int min(int x, int y, int z) { x = x<y ?x :y; return x<z ?x :z; } } | cs |