Baekjoon 11660 구간 합 구하기 5 JAVA

11660번: 구간 합 구하기 5

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

 

조건

[입력]

첫째 줄에 표의 크기 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)까지 합을 구해 출력한다.

 

풀이

해당 문제는 2차원 배열이 주어졌을 때 x1, y1 ~ x2, y2 모두를 더한 값을 구하는 문제다.

해당 문제는 dp를 이용하여 해결했고 아래와 같은 방식으로 접근했다.

 

일단 2차원 배열 값을 입력함과 동시에 해당 위치까지의 2차원 배열의 합을 저장해준다.

 

점화식 = 입력값, 한 칸 왼쪽 값, 한 칸 위쪽 값을 더해준 뒤 왼쪽 위 대각선 값을 빼준다. (중복이므로)

dp[i][j] = Integer.parseInt(st.nextToken()) + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

 

이후 최종 출력 값에 대해선 아래 표를 참고하여 만약 2 2 3 4를 구하고자 할 때 처음 빨간색에서 초록색과 파란색 부분을 빼주면 된다. 하지만 1 1에 있는 1 값을 두 번 빠지게 되므로 다시 한번 더해준다.

점화식

dp[c][d] - dp[c][b-1] - dp[a-1][d] + dp[a-1][b-1]

코드

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

public class Main {
    public static void main(String[] args) throws Exception{
        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][N+1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken()) + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            System.out.println(dp[c][d] - dp[c][b-1] - dp[a-1][d] + dp[a-1][b-1]);
        }
    }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드