[백준] 2167 2차원 배열의 합 - Java

 

 

 

문제 출저 

https://www.acmicpc.net/problem/2167

2167번: 2차원 배열의 합

 

 

 

 

문제 풀이

숫자가 있는 2차원 배열이 주어집니다.

이 때, 범위가 주어지는데 범위에 포함된 숫자들의 합을 구하는 것이 문제의 요구사항 입니다.

 

누적합으로 풀었습니다.

prefix 2차원 배열을 만들어 i,j 지점에 0.0 부터 i,j 까지의 모든 숫자를 더한 값을 저장합니다.

그 후, 누적합 배열을 이용해 수식을 만들어 정답을 구했습니다.

 

 

 

소스 코드

package baekjoon.backjoon10.day1120.day20;

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

/*
2차원 배열의 합
https://www.acmicpc.net/problem/2167
 */
public class B2167 {

    static int n,m;
    static int[][] board;
    static int[][] prefix;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = 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++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        prefix = new int[n+1][m+1];
        prefix[1][1] = board[1][1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                prefix[i][j] = board[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
            }
        }


        int testcase = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < testcase; i++) {
            st = new StringTokenizer(br.readLine());
            int y1 = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());

            sb.append(calculation(y1, x1, y2, x2)).append("\n");
        }

        System.out.println(sb.toString());

    }

    public static int calculation(int y1, int x1, int y2, int x2) {
        int result = prefix[y2][x2] - prefix[y2][x1-1] - prefix[y1-1][x2] + prefix[y1-1][x1-1];
        return result;
    }

}