[백준] 1451 직사각형으로 나누기 java

2022. 3. 4. 23:25· Dev/PS

import java.io.*;
import java.util.*;

public class DivisionSquare {
    static BufferedReader br;
    static StringTokenizer st;
    static int N, M;
    static int[][] arr;
    static long[][] sum;
    static long ans = -1;

    public static void main(String[] args) throws IOException{
        input();
        solve();
        System.out.println(ans);
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N+1][M+1];
        sum = new long[N+1][M+1];
        for(int[] a : arr) {
            Arrays.fill(a, 0);
        }
        for(int i = 1; i <= N; i++) {
            String s = br.readLine();
            for(int j = 1; j <= M; j++) {
                arr[i][j] = s.charAt(j-1) - '0';
            }
        }
    }


    public static void solve() {
        //1. sum 구하기
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (long)arr[i][j];
            }
        }

        //2. 6개의 경우 별로 곱의 합 구하기

        //가로 3개
        for(int i = 1; i <= N-2; i++) {
            for(int j = i+1; j <= N-1; j++) {
                long r1 = sum(1, 1, i, M);
                long r2 = sum(i+1, 1, j, M);
                long r3 = sum(j+1, 1, N, M);
                ans = Math.max(ans, r1 * r2 * r3);
            }
        }

        //세로 3개
        for(int i = 1;  i <= M-2; i++) {
            for(int j = i+1; j <= M-1; j++) {
                long r1 = sum(1, 1, N, i);
                long r2 = sum(1, i+1, N, j);
                long r3 = sum(1, j+1, N, M);
                ans = Math.max(ans, r1 * r2 * r3);
            }
        }

        //ㅜ형
       for(int i = 1; i <= N-1; i++) {
           for(int j = 1; j <= M-1; j++) {
               long r1 = sum(1, 1, i, M);
               long r2 = sum(i+1, 1, N, j);
               long r3 = sum(i+1, j+1, N, M);

               ans = Math.max(ans, r1*r2*r3);
           }
       }
        //ㅗ형
       for(int i = N; i > 1; i--) {
           for(int j = 1; j <= M-1; j++) {
               long r1 = sum(i, 1, N, M);
               long r2 = sum(1, 1, i-1, j);
               long r3 = sum(1, j+1, i-1, M);

               ans = Math.max(ans, r1*r2*r3);
           }
       }

       //ㅏ형
        for(int i = 1; i <= M-1; i++) {
            for(int j = 1; j <= N-1; j++) {
                long r1 = sum(1, 1, N, i);
                long r2 = sum(1, i+1, j, M);
                long r3 = sum(j+1, i+1, N, M);

                ans = Math.max(ans, r1*r2*r3);
            }
        }

        //ㅓ형
        for(int i = M; i > 1; i--) {
            for(int j = 1; j <= N-1; j++) {
                long r1 = sum(1, i, N, M);
                long r2 = sum(1, 1, j, i-1);
                long r3 = sum(j+1, 1, N, i-1);

                ans = Math.max(ans, r1*r2*r3);
            }
        }
    }

    public static long sum(int x1, int y1, int x2, int y2) {
        return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
    }
}

완전탐색 문제이고 조건 분기가 꽤 있는 문제이다. 나는 어떻게 풀어야할지 아이디어가 떠오르지 않아서 다른 분들의 코드를 보면서 풀었다. 관건은 모든 경우의 수를 적절히 알고 좌표의 위치를 틀리지 않고 모두 돌 수 있어야 한다.

 

우선 해야할 일은 크게 2가지다.

 

1. 각 좌표의 위치마다 sum 구해놓기

2. 6가지의 경우의 수에서 가질 수 있는 경우의 수 모두 구하기

 

1번은 알고리즘이 좀 더 효율성을 내기 위해서 미리 합을 구해놓는 것이다. 

만약 2번에서 경우의 수 마다 매번 2중 for문을 돌리면서 답을 구해야 한다면 꽤나 비효율적이다. 하지만 미리 구해 놓는다면 단 한번의 연산만으로 해당 위치의 sum값을 구할 수가 있다. 시간복잡도면에서 훌륭한 전략이다.

 

2번은 6가지의 경우로 나눠서 생각을 할 수가 있다.

 

1. 가로 3개

2. 세로 3개

3. 세로 1개, 가로 2개

4. 3번의 반대

5. 가로 1개, 세로 2개

6. 5번의 반대

 

이렇게 6개의 경우에서 또 직사각형의 크기마다 sum을 구해서 현재 최대값과 계속해서 비교한다.

저작자표시 (새창열림)

'Dev > PS' 카테고리의 다른 글

[백준] 1697 숨바꼭질 java  (0) 2022.03.09
[백준] 10971 외판원 순회 2 java  (0) 2022.03.05
[백준] 1107 리모컨 java  (0) 2022.02.22
[백준] 2661 좋은수열 java  (0) 2022.02.10
[백준] 14888 연산자 끼워넣기 java  (0) 2022.02.08
'Dev/PS' 카테고리의 다른 글
  • [백준] 1697 숨바꼭질 java
  • [백준] 10971 외판원 순회 2 java
  • [백준] 1107 리모컨 java
  • [백준] 2661 좋은수열 java
풋데브
풋데브
지속가능한 삶
풋데브
지루함에 익숙해지자
풋데브
전체
오늘
어제
  • 분류 전체보기 (90)
    • 일상 (4)
    • 후기 (2)
    • 운동 (0)
    • Dev (84)
      • PS (72)
      • CS (0)
      • Java (1)
      • Spring (0)
      • DB (4)
      • Test (2)
      • Web (0)
      • 트러블 슈팅 (2)
      • Etc (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 투포인터
  • 백준
  • BFS
  • 백엔드
  • 알고리즘
  • 조합
  • DFS
  • 다이나믹프로그래밍
  • 백트래킹
  • 자바
  • 너비우선탐색
  • 코테
  • 코딩테스트
  • java
  • algorithm
  • codingtest
  • 개발자
  • 구현
  • BOJ
  • combination
  • Implement
  • 깊이우선탐색
  • DP
  • programming
  • Developer
  • bruteforce
  • 그래프
  • 완전탐색
  • graph
  • 자료구조

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
풋데브
[백준] 1451 직사각형으로 나누기 java
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.