[백준, Java] 1184번, 귀농, (누적합)

문제 링크

1184번: 귀농

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 땅은 N × N의 정사각형이며, 땅은 1 × 1 단위로 나누어져 있습니다.

2. 각 땅은 수익이 존재하며, 음수가 될 수도 있습니다.

3. 땅을 선영이와 선근이에게 빌려주며, 땅은 항상 직사각형입니다.

4. 두 땅은 꼭짓점 하나에서 만나야 합니다.

5. 땅을 빌려주었을 때 수익이 같은 방법의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 꼭짓점을 기준으로 땅을 빌려주는 경우를 탐색합니다.

 

3. 탐색을 통해 얻은 같은 수익을 내는 방법의 개수를 결과로 출력합니다.

 

꼭짓점 기준 탐색하기

 

빌려준 두 땅은 하나의 꼭짓점을 지나야 하기 때문에, 각 꼭짓점을 기준으로 땅을 주는 경우는 정해져있습니다.

 

외곽 꼭짓점이 선택되지 않은 이유는 해당 꼭짓점을 지나는 2개의 땅으로 만들 수 없기 때문입니다.

 

땅을 나누어 주는 방법은 2가지가 있습니다.

 

1. ↖, ↘ 영역의 땅 배분

 

 

 

 

2. ↙, ↗ 영역의 땅 배분

 

 

2가지 땅을 빌려주는 경우에서 영역을 좁혀가면서 수익이 같은 것을 탐색하면 됩니다.

 

수익 계산하기(누적합)

 

영역에 대한 수익을 구하기 위해서 반복되는 탐색을 최소화시키기 위해서 2차원 배열 누적합을 이용하였습니다.

 

 

점화식 : DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + arr[i][j];

 

※ DP[i-1][j-]을 빼는 이유는 중복된 영역이기 때문에 2번 더해져서 빼주는 것입니다.

 

 

누적합 결과로 구역의 수익을 구할 때(구할 영역 : 파란색 영역)

 

 

(x1, y1) - (x2, y2)의 영역의 수익

 

수익 : DP[y2][x2] - DP[y2][x1-1] - DP[y1-1][x2] + DP[y1-1][x1-1]

 

 

 

위 점화식을 토대로 수익의 2차원 누적합을 구한 뒤 영역의 수익을 구하였습니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 3

 

 

 

 

 

2. 꼭짓점을 기준으로 땅을 빌려주는 경우를 탐색합니다.

 

누적합을 이용해서 먼저, 영역의 수익에 대한 정보를 정의합니다.

 

 

 

만날 수 있는 꼭짓점

 

(1, 1) 꼭짓점일 때

 

 

파란색 수익 : DP[1][1] - DP[1][0] - DP[0][1] + DP[0][0] = 1

 

주황색 수익 : DP[3][3] - DP[3][1] - DP[3][1] + DP[1][1] = 19

 

두 땅은 수익이 같지 않습니다.

 

 

 

파란색 수익 : DP[1][1] - DP[1][0] - DP[0][1] + DP[0][0] = 1

 

주황색 수익 : DP[2][3] - DP[2][1] - DP[1][3] + DP[1][1] = 7

 

두 땅은 수익이 같지 않습니다.

파란색 수익 : DP[1][1] - DP[1][0] - DP[0][1] + DP[0][0] = 1

 

주황색 수익 : DP[3][2] - DP[3][1] - DP[1][2] + DP[1][1] = 7

 

두 땅은 수익이 같지 않습니다.

 

파란색 수익 : DP[1][1] - DP[1][0] - DP[0][1] + DP[0][0] = 1

 

주황색 수익 : DP[2][2] - DP[2][1] - DP[1][2] + DP[1][1] = 3

 

두 땅은 수익이 같지 않습니다.

 

 

 

위와 같이 모든 꼭짓점을 탐색하시면 됩니다.

 

 

 

3. 탐색을 통해 얻은 같은 수익을 내는 방법의 개수를 결과로 출력합니다.

 

구한 영역

 

(0,0)-(1,1), (2,2)-(2,2)

(1,0)-(1,0), (0,1)-(0,1)

(2,0)-(2,0), (1,1)-(1,1)

(1,1)-(1,1), (0,2)-(0,2)

(2,1)-(2,1), (1,2)-(1,2)

(2,0)-(2,1), (0,2)-(1,2)

(1,0)-(2,0), (0,1)-(0,2)

 

 

7 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 땅의 수익 정보를 띄어쓰기 기준 나누어줍니다.
  
• 땅 수익에 2차원 누적합을 구합니다.
• 꼭짓점을 기준으로 search함수를 이용하여 (↖↘),(↙↗)영역을 탐색합니다.
• 탐색을 통해 얻은 같은 수익을 가진 경우의 개수를 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 영역에 존재하는 수익을 구한 뒤 같은 경우의 수를 계산합니다.
• compare함수는 각 방향에 대한 가능한 영역에 수익을 구합니다.
• calArea함수는 땅 영역의 수익을 점화식으로 계산합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    //↖↘↙↗ 순서로 탐색해야하는 영역 관련 y, x 변경값
    static int[] dr = {-1, 1, 1, -1};
    static int[] dc = {-1, 1, -1, 1};
    static int[][] DP;	//누적합 저장할 배열
    static int N;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        DP = new int[N+1][N+1];
        StringTokenizer st;
        //수익 누적합 구하기
        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=N;j++){
                DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + Integer.parseInt(st.nextToken());
            }
        }
        int cnt = 0;
        //각 꼭짓점 영역 비교하기
        for(int i=1;i<N;i++){
            for(int j=1;j<N;j++){
                //search(i, j, 0, 1) : ↖↘
                //search(i, j, 2, 3) : ↙↗
                cnt += search(i, j, 0, 1) + search(i, j, 2, 3);
            }
        }
        //개수 BufferedWriter 저장
        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
    //꼭짓점 기준 영역 탐색하는 함수
    static int search(int y, int x, int d1, int d2){
        int cnt = 0;
        Map<Integer, Integer> left = new HashMap<>();
        Map<Integer, Integer> right = new HashMap<>();
        //↖↘영역 탐색
        if(d1 == 0 && d2 == 1){
            compare(y, x, d1, left);
            compare(y+1, x+1, d2, right);
        }else{	//↙↗ 영역 탐색
            compare(y+1, x, d1, left);
            compare(y, x+1, d2, right);
        }

        //수익 같은 경우 구하기
        for(int area : left.keySet()){
            if(right.containsKey(area)){
                cnt += left.get(area) * right.get(area);
            }
        }
        return cnt;
    }
    //각 영역에 존재하는 수익 구하는 함수
    static void compare(int y, int x, int direction, Map<Integer, Integer> map){
        int r = y;
        while(r > 0 && r <= N ){
            int temp;
            int c = x;
            while(c > 0 && c <= N){
                if(direction == 0) {	//↖ 영역 수익 구하기
                    temp = calArea(r, c, y, x);
                } else if(direction == 1) {	//↘ 영역 수익 구하기
                    temp = calArea(y, x, r, c);
                } else if(direction == 2) {	//↙ 영역 수익 구하기
                    temp = calArea(y, c, r, x);
                } else {	//↗ 영역 수익 구하기
                    temp = calArea(r, x, y, c);
                }
                map.put(temp, map.getOrDefault(temp, 0) + 1);
                c += dc[direction];	//x축 이동
            }
            r += dr[direction];		//y축 이동
        }
    }
    //영역 수익 구하는 함수
    static int calArea(int r1, int c1, int r2, int c2){
        return DP[r2][c2] - DP[r1-1][c2] - DP[r2][c1-1] + DP[r1-1][c1-1];
    }
}