[BOJ/JAVA] 백준 1451 / 직사각형으로 나누기

• 시도횟수: 2회
• 시간: 약 1시간
• 만족도: ★★☆☆☆
• 힌트 키워드: #그리디, #경우

문제링크 : https://www.acmicpc.net/problem/1451

인트로

첫 알고리즘 게시물로 완벽한 코드로 작성하고 싶었지만, 문제가 정말 내 스타일이 아니었다^^,, 내가 생각한 접근 방법을 계속 부정하면서 다른 방법을 찾으려고 했지만, 결국은 다시 돌아와서 체념하면서 풀었다. 숏코딩을 고집하는 나는 이런 경우의 수를 나눠야 하는 문제 너무 싫다,,ㅎ

문제 요약

• Input: N*M의 큰 직사각형이 주어짐
• output
  • 큰 직사각형을 3개의 작은 직사각형으로 나눔.
  • 각각의 작은 직사각형에 있는 모든 숫자들을 더함.
  • 그 3개의 숫자들을 곱했을 때, 나올 수 있는 최댓값을 출력.

접근 방식

1. 경우 나누기

   

   숫자들이 음수가 되는 경우가 없기 때문에, 작은 직사각형이 큰 직사각형을 다 덮지 않는 경우는 없다. 따라서, 최댓값이 나올 수 있는 경우는 다음 6가지의 경우로 나눌 수 있다. 그리고 남은건 빡구현,,,

2. 코드를 줄이기 위한 알고리즘 모색

   1번의 경우 나누기가 바로 생각 났었지만, 당연히 더 좋은 방법이 있을 것이라고 생각하고, 계속 생각을 해봤다. 열방향으로 나누는 것(a)과 행방향으로 나누는 것(b)을 합쳤을 때 2가 되도록 해서, 조합으로 풀어볼까 생각을 했는데, 더 코드가 복잡하고 덜 직관적일 것이라고 판단하고, 1번으로 돌아가 빡구현을 했다. 이 고민을 한다고 시간이 많이 소요된 것 같다.

오답 원인

오답: 1회

1. int 사용

   곱연산이기 때문에, 값이 매우매우 커진다. 하지만,,, 나는 바보같이 int를 사용했다,,, 그래서 틀렸다,,,

   정말,, 자바를 하면서 잊을 만 하면 등장하는 오답 원인이다. 값이 클 때 int가 아닌 long을 쓰는 것 명심 또 명심,,

정답 코드

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

public class Main {
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        long ans=0;

        for (int i = 0; i < N; i++) {
            char[] cArr = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                arr[i][j]=cArr[j]-'0';
            }
        }

        for (int i = 0; i < N-1; i++) {
            for (int j = i+1; j < N; j++) {
                if(j==N-1){
                    for (int k = 0; k < M-1; k++) {
                        ans = Math.max(ans, sum(0,0,i,k)*sum(0,k+1,i,M-1)*sum(i+1,0,N-1,M-1));
                        ans = Math.max(ans, sum(i+1,0,N-1,k)*sum(i+1,k+1,N-1,M-1)*sum(0,0,i,M-1));
                    }
                } else {
                    ans = Math.max(ans, sum(0,0,i,M-1)*sum(i+1,0, j,M-1)*sum(j+1,0,N-1,M-1));
                }
            }
        }
        for (int i = 0; i < M-1; i++) {
            for (int j = i+1; j < M; j++) {
                if(j==M-1){
                    for (int k = 0; k < N-1; k++) {
                        ans = Math.max(ans, sum(0,0,k,i)*sum(k+1,0,N-1,i)*sum(0,i+1,N-1,M-1));
                        ans = Math.max(ans, sum(0,i+1,k,M-1)*sum(k+1,i+1,N-1,M-1)*sum(0,0,N-1,i));
                    }
                } else {
                    ans = Math.max(ans, sum(0,0,N-1,i)*sum(0,i+1, N-1,j)*sum(0,j+1,N-1,M-1));
                }
            }
        }
        System.out.print(ans);
    }

    static long sum(int x1, int y1, int x2, int y2){
        int s=0;
        for (int i = x1; i <= x2; i++) {
            for (int j = y1; j <= y2; j++) {
                s+=arr[i][j];
            }
        }
        return s;
    }
}

코드에 대한 분석

1. 시간 줄이기

   N과 M이 그렇게 큰 편이 아니라서, 누적합을 안 사용하긴 했는데, 누적합을 사용하면 시간을 줄일 수 있을 듯 하다.

2. 리팩토링

   메인 로직에서 for문 2개가 거의 중복되는게 너무 거슬린다. sum(a,b,c,d)로 놓고, 행방향일 때 열방향일 때로 경우를 나눌 수 있게 메서드를 작성하면 코드가 훨씬 간결해질 듯 싶다. (하지만, 이 문제에 이 정도의 정성을 쓰고 싶진 않기 때문에 잠시 Pass,,)

결과