백준 acm 1915 가장 큰 정사각형

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;     } } Colored by Color Scripter

cs