[백준(baekjoon) 1184] 귀농

문제

백준 1184

N x N 크기의 땅은 각 단위 정사각형 (i, j)당 의 수익을 가진다.
이 땅을 변에 평행한 직사각형 땅 두개로 나누고자 한다.
단, 두 땅은 반드시 한 꼭지점에서만 만나고, 총 땅의 수익이 같아야 한다.
조건에 맞게 나눌 수 있는 방법의 수를 출력하라.

• N <= 50
• < = 1,000 && >= -1,000

해결

알고리즘

배열을 활용한 구현 문제이다.
DP를 활용해 풀었다.

방법

생각을 더 깊게할수록 복잡해지는 문제 같다.
다시 처음으로 돌아와서 아래처럼 풀었는데, N의 범위가 작아서 시간초과가 나지 않았다.
중복코드를 줄이기 위해 배열을 활용해 방향키 설정(?)을 해주었다.

1.직사각형이 공유하는 꼭지점이 반드시 하나이다.
즉, 전체 정사각형 땅에서 공유 꼭지점이 될 수 있는 건 아래와 같다.

2.각 꼭지점을 기준으로 아래처럼 4방향으로 확장한다.
- 방향마다 꼭지점을 반드시 포함하는 가능한 직사각형의 총 수익을 구한다.
- 각 구역별 x축과 y축의 확장 방향은 아래와 같다.

3.확장 방향에 따라 열 -> 행 순서로 이동하며 각 지점을 끝으로하고 꼭지점을 시작으로 하는 직사각형의 총 수익을 구한다.

이 부분은 예제를 통해 쉽게 살펴보자.
↖︎ 방향으로 확장 할 때, 자주색 사각형의 총 수익은 다음과 같다.

• 자주색 사각형 : 해당 지점을 끝으로하고 꼭지점을 시작으로 하는 구하고자 하는 사각형
• 파란색 사각형 : 구하고자 하는 사각형에서 해당 행 부분을 제외한 사각형
• 하늘색 사각형 : 구하고자 하는 사각형에서 해당 행 부분

파란색 사각형과 하늘색 사각형은 아래 그림의 원리로 구할 수 있다.

즉, 자신의 행 부분을 제외한 부분은 이미 구해져있으므로 이를 활용한다. (= DP)

4.꼭지점 기준으로 ↖︎ 와 ↘︎ , ↗︎ 와 ↙︎ 의 총 수익을 비교한다.
총 수익이 일치할 경우 count를 늘린다.

구현 java

참고
기준은 꼭지점을 기준으로 왼쪽 상단에 위치한 1x1 정사각형 위치입니다.

1.import java.util.*;
2.
3.public class Main {
4.    static int[][] map; // 입력 땅 정보
5.    static int n;
6.    // 확장 방향 ↖︎↗︎↙︎↘︎ 에 맞는 x, y축 이동 방향
7.    static int[] fx = { -1, 1, -1, 1};
8.    static int[] fy = { 1, 1, -1, -1};
9.    // 확장의 시작점을 구하기 위해 기준(꼭지점)에 더해줄 값
10.    static int[] dx = { 0, 1, 0, 1};
11.    static int[] dy = { 0, 0, -1, -1};
12.
13.    public static void main(String[] args) {
14.        Scanner sc = new Scanner(System.in);
15.        n = sc.nextInt();
16.        // 대각선 확장을 쉽게 구하기 위해 0은 비워둘 것
17.        map = new int[n + 1][n + 1];
18.        // input
19.        for (int i = 1; i <= n; i++) {
20.            for (int j = 1; j <= n; j++) {
21.                map[i][j] = sc.nextInt();
22.            }
23.        }
24.
25.        int allCount = 0;
26.        // 교차점 순회
27.        for (int i = 2; i <= n; i++) {
28.            for (int j = 1; j < n; j++) {
29.                // 교차점 기준으로 ↖︎ vs ↘︎, ↗︎ vs ↙︎ 비교한 총 경우의 수
30.                allCount += pointCount(i, j);
31.            }
32.        }
33.        System.out.println(allCount);
34.    }
35.
36.    private static int pointCount(int y, int x) {
37.        int same = 0;
38.        // 첫번째 : ↖︎(0) vs ↘︎(3), 두번째 : ↗︎(1) vs ↙︎(2)
39.        for (int dir = 0; dir < 2; dir++) {
40.            // 왼쪽 방향과 오른쪽 방향에서 가능한 직사각형의 총 수익을 담는 배열
41.            ArrayList<Integer> left = getRevenue(y + dy[dir], x + dx[dir], dir);
42.            int rd = 3 - dir;
43.            ArrayList<Integer> right = getRevenue(y + dy[rd], x + dx[rd], rd);
44.
45.            // 왼쪽 vs 오른쪽 각 직사각형의 수익을 비교.
46.            for (int l : left) {
47.                for (int r : right) {
48.                    if (l == r) same++;
49.                }
50.            }
51.        }
52.
53.        return same;
54.    }
55.
56.    private static ArrayList<Integer> getRevenue(int y, int x, int dir) {
57.        int[][] revMap = new int[n + 1][n + 1]; // 이전 확장 값을 저장하기 위한 배열
58.        ArrayList<Integer> revenue = new ArrayList<>(); // 가능한 직사각형 수익 저장
59.        for (int i = y; fy[dir] > 0 ? i <= n : i > 0; i += fy[dir]) {
60.            int horSum = 0; // 각 행 확장 값 저장 용도
61.            for (int j = x; fx[dir] > 0 ? j <= n : j > 0; j += fx[dir]) {
62.                horSum += map[i][j];
63.                // revMap[i - fy[dir]][j] : 확장 방향 기준, 해당 열 이전 행까지의 총 수익
64.                // 새로운 직사각형 = (특정 열까지)(현재 행의 총 수익 + 이전 행까지의 총 수익)
65.                revMap[i][j] = revMap[i - fy[dir]][j] + horSum;
66.                revenue.add(revMap[i][j]);
67.            }
68.        }
69.        return revenue;
70.    }
71.}
72.

결과

1. 위의 코드
2. 각 구역별 총 수익을 정렬한 후, 비교 범위를 줄인 코드