(백준/자바) 힌트문제3 02. 2차원배열 - 백준 2167번 문제 : 2차원 배열의 합

2167번: 2차원 배열의 합 (acmicpc.net)

2167번: 2차원 배열의 합

간단하게 풀었다. 근데 다른 알고리즘 같은 거 없이 그냥 단순 이중 for문 문제는 아닐 것 같은데 ...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class TwoArray_02 {
    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());
        int arr[][] = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int k = Integer.parseInt(br.readLine());

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken())-1;
            int q = Integer.parseInt(st.nextToken())-1;
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            int answer = 0;
            for (int j = p; j <= x; j++) {
                for (int l = q; l <= y ; l++) {
                    answer += arr[j][l];
                }
            }
            System.out.println(answer);
        }
    }
}

3중 for문을 하면 시간초과가 난다는데 이건 시간초과가 안 난다.

다이나믹 알고리즘을 쓰면 더 빠르게 풀 수 있대 ! 공부해서 다시 해보자

 

---

* dp 테이블을 구성 int dp[][] = new int[N + 1][M + 1];

for(int j = 1; j <= M; j++) {
	dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + Integer.parseInt(st.nextToken());
}

여기가 핵심같다. 해당 i,j 번째 dp 테이블에 값을 저장할 때는 

이런식으로 왼쪽으로 한 칸까지의 값 + 위 쪽으로 한 칸까지의 값 - 대각선 위쪽 까지의 값...

이렇게 명쾌하게 이해되는게 오랜만이다. 너무 신나네

그러고 바로 막혔다.

이제 얘네는 누적합이 저장되어있는데 여기서 구간에 따른 값들을 어떻게 꺼낼 것이냐...

뭐야 ㅠ 이미 찾아놓고 빼기 잘못해서 헤메고 있었네.. 졸린가보다 얼른하고 자야지

이렇게 ! 해주면 된다. 검정 동그라미 + 빨간 동그라미 + 파란동그라미 - 겹치는 부분

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Practice {
    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());
        int dp[][] = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + Integer.parseInt(st.nextToken());
            }
        }
        int k = Integer.parseInt(br.readLine());
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int answer = 0;

            answer = dp[x][y] - dp[p-1][y] - dp[x][q - 1] + dp[p - 1][q - 1];
            System.out.println(answer);
        }
    }
}

끝 !

 

아래는 처음 for문 돌려서 푼 건데 위에 다이나믹으로 풀었을 때가 정말 시간이 빨라진 걸 볼 수 있었다 !!