[코드트리] 겹치지 않는 두 직사각형

문제링크

문제 설명

n m 배열에 n m개의 숫자가 주어진다.
이 숫자들을 겹치지 않는 두개의 직사각형 모양으로 감싸 그 속에 있는 숫자의 합을 더한다.
이 두 직사각형 속에 있는 수가 최대가 되는 경우를 구해라

풀이 과정

• 이전에 마름모 모양으로 숫자의 합을 더하는 것처럼 구할 수 있는 직사각형의 경우의 수를 생각 -> 한개의 직사각형의 최대값은 구할 수 있으나, 두개의 직사각형의 경우를 찾기 어려움
• 위의 경우에서 한개의 직사각형 값을 찾고, 나머지 부분에서 다른 직사각형을 찾으려 함 -> 기존의 직사각형과 겹치지 않아야하고, 경우의 수가 많아서 모든 부분을 구현하기 어렵다구 판단
• 특정한 위치에서의 모든 경우를 생각했었는데, 모든 점에서의 경우를 생각하는 것으로 변경 + 첫번째 직사각형과 두번째 직사각형이 겹치지 않는지 판단 -> 원하는 값을 찾을 수 있음 !

풀이 코드

마지막 점(모든 점에서의 경우 판단 + 겹치지 않는지 판단) 풀이 코드

    public static int find_max(){
        int ret = Integer.MIN_VALUE;

        for (int r1 = 0; r1 < n; r1++){
            for (int c1 = 0; c1 < m; c1++){
                for (int r2 = r1; r2 < n; r2++){
                    for (int c2 = c1; c2 < m; c2++){
                        int firSum = circulate(r1, c1, r2, c2);

                        for (int x1 = 0; x1 < n; x1++){
                            for (int y1 = 0; y1 < m; y1++){
                                for (int x2 = x1; x2 < n; x2++){
                                    for (int y2 = y1; y2 < m; y2++){
                                        if (right(r1, c1, r2, c2, x1, y1, x2, y2)){
                                            int secSum = circulate(x1, y1, x2, y2);
                                            ret = Math.max(ret, firSum + secSum);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }


        return ret;
    }

• 정말 모든 점에서 판단 r1, c1, r2, c2가 첫번째 직사각형, x1, y1, x2, y2가 두번째 직사각형의 점! -> 이 점에 속하는 값들을 더하고, 사각형이 겹치지 않는지 판단.

    public static boolean right(int r1, int c1, int r2, int c2,
                                int x1, int y1, int x2, int y2){
        if (x1 > r2 || x2 < r1 || y1 > c2 || y2 < c1)
            return true;
        return false;
    }

두 점이 겹치지 않는지 판단하는 코드

• x1 > r2 첫번째 사각형보다 두번째 사각형이 아래에 위치하는 경우
• x2 < r1 두번째 사각형이 첫번째 사각형 아래에 위치하는 경우
• y1 > c2 첫번째 사각형이 두번째 사각형의 왼쪽에 위치하는 경우
• y2 < c1 두번째 사각형이 첫번째 사각형의 왼쪽에 위치하는 경우

문제 해설 풀이와 차이점

해설에서는 겹치는 구간을 리스트로 처리하여방문한 부분을 +1 해준다.
만약 리스트 속 값이 2가 있는 경우는 겹치는 부분이 존재한다는 뜻이다.