[랜덤 마라톤] 행렬 찾기(1687)

1. 문제 풀이 아이디어

• 누적 합을 사용하여 문제를 해결한다.

• 주어진 2차원 배열에서 '0'을 1로 바꾸고, 이를 통해 형성될 수 있는 행렬 크기의 최대값을 찾는다.

• 누적 합을 활용해 각 부분 행렬을 빠르게 계산하고, 그 중에서 조건에 맞는 최대값을 구한다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            String s = bufferedReader.readLine();
            for (int j = 1; j <= m; j++) {
                arr[i][j] = arr[i][j - 1] + ('1' - s.charAt(j - 1));
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] += arr[i - 1][j];
            }
        }
        int result = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j++) {
                int size = 0;
                for (int k = 1; k <= n; k++) {
                    int chk = arr[k][j] - arr[k][i - 1] - arr[k - 1][j] + arr[k - 1][i - 1];
                    if (chk == j - i + 1) {
                        size += chk;
                        result = Math.max(result, size);
                    } else {
                        size = 0;
                    }
                }
            }
        }
        System.out.println(result);
        bufferedReader.close();
    }
}

3. 정리

• 주어진 행렬에서 '0'을 1로 변환하여 누적 합 배열을 만든다. 이를 통해 각 구간에 대한 합을 빠르게 계산할 수 있다.

• 두 개의 열을 선택하여 가능한 모든 부분 행렬을 계산한다.

• 두 개의 열 인덱스 i, j를 선택하여 모든 가능한 부분 행렬을 계산한다. 각 행에 대해 해당 열 범위의 합을 구한 후, 모든 값이 '1'로 채워졌다면 그 크기를 size에 누적하여 최대 값을 찾는다.

• 부분 행렬의 크기를 계산하면서, 그 중에서 가장 큰 크기를 result에 저장한다.

• 계산한 최대 크기를 출력한다.