[알고리즘] 11660번

오늘 풀어볼 문제는 백준 11660번 문제 "구간 합 구하기 5" 이다.

이 문제는 실버1 문제이고 구간 합 구하기 문제이다.

문제

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

📌첫 번째 도전📌
앞에서 풀었던 11659번이랑 같은 방향으로 풀려고 각 열의 합을 모두 더하는 방식으로 풀었다.
하지만.. 생각처럼 계산이 안 됐고 이 방향이 틀리다는 걸 깨달았다.
일단 적은 코드를 첨부하지만... 작동도 안되는 코드이다 ㅎㅎ

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

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        long[][] arr = new long[N+1][N+1];

        for (int i=1; i<=N; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j=1; j<=N; j++) {
                if(j == 1) {
                    arr[j][i] = arr[N][i-1] + Integer.parseInt(stringTokenizer.nextToken());
                }
                else {
                    arr[j][i] = arr[j-1][i] + Integer.parseInt(stringTokenizer.nextToken());
                }
            }
        }

        for(int i=0; i<M; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int x1 = Integer.parseInt(stringTokenizer.nextToken());
            int y1 = Integer.parseInt(stringTokenizer.nextToken());
            int x2 = Integer.parseInt(stringTokenizer.nextToken());
            int y2 = Integer.parseInt(stringTokenizer.nextToken());

            System.out.println();
        }
    }
}

코드를 여기까지 작성하고 방향을 틀었다.. ㅎ

📌두 번째 도전📌
dp를 이용하는 방향으로 틀어보았다.

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

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        long[][] arr = new long[N+1][N+1];

        for (int i=1; i<=N; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j=1; j<=N; j++) {
                arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        long[][] dp = new long[N+1][N+1];

        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];
            }
        }

        for(int i=0; i<M; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int x1 = Integer.parseInt(stringTokenizer.nextToken());
            int y1 = Integer.parseInt(stringTokenizer.nextToken());
            int x2 = Integer.parseInt(stringTokenizer.nextToken());
            int y2 = Integer.parseInt(stringTokenizer.nextToken());

            System.out.println(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]);
        }
    }
}

dp 배열의 값은 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + array[i][j] 이다.
이 이유는 주변의 값의 합으로 dp[i][j]가 결정나기 때문이다.
위 공식을 이용해서 dp 배열을 만든 후 값을 출력을 할 때는 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] 이 공식으로 출력을 한다.
위 공식은 dp배열에서 원하는 값을 뽑아내기 위해 중복되는 값들을 모두 없애주는 작업이다.

그렇게 하면 정상적으로 출력이 된다.

컴파일 에러는 import 내용을 넣어주지 않아서 발생한거다 ㅎㅎ

[문제 출처] https://www.acmicpc.net/problem/11660