문제 설명

문제 바로가기
2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

생각해보기

딱 생각나는 것은 주어지는 데로 배열을 만들고 각각의 합을 구하는 것이다.

다 풀고 다른 사람의 풀이를 보니 더 좋은 풀이를 발견했다.

원래의 풀이와 다른 풀이를 둘 다 올린다.

풀이

원래의 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Tokenizer tokenizer = new Tokenizer(br);
        int N = tokenizer.nextInt();
        int M = tokenizer.nextInt();
        int[][] arr = new int[N][M];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                arr[i][j] = tokenizer.nextInt();
            }
        }

        int K = tokenizer.nextInt();
        StringJoiner sj = new StringJoiner(System.lineSeparator());
        for(int k = 0; k < K; k++) {
            int i = tokenizer.nextInt();
            int j = tokenizer.nextInt();
            int x = tokenizer.nextInt();
            int y = tokenizer.nextInt();
            int sum = 0;
            for(int r = i-1; r < x; r++) {
                for(int c = j-1; c < y; c++) {
                    sum+=arr[r][c];
                }
            }
            sj.add(String.valueOf(sum));
        }
        System.out.println(sj);
    }

    public static class Tokenizer {
        private BufferedReader br;
        private StringTokenizer st;

        public Tokenizer(BufferedReader br) {
            this.br = br;
        }

        public int nextInt() throws IOException {
            if(st == null || !st.hasMoreTokens()) {
                this.st = new StringTokenizer(br.readLine());
                return nextInt();
            }
            return Integer.parseInt(st.nextToken());
        }
    }
}

주어진 i,j,x,y에 대해 각각 sum을 구한다.

하지만 배열 arr가 각 요소를 가지는 것보다 애초에 앞선 요소부터 그 요소까지의 합을 가지고 있으면 i,j,x,y가 주어졌을 때 다시 합을 구할 필요가 없어진다.

좀 더 좋은 풀이

배열에 누적 합을 저장한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Tokenizer tokenizer = new Tokenizer(br);
        int N = tokenizer.nextInt();
        int M = tokenizer.nextInt();
        int[][] arr = new int[N+1][M+1];
        int sum = 0;
        for(int i = 1; i <= N; i++) {
            arr[i][0] = sum;
            for(int j = 1; j <= M; j++) {
                sum += tokenizer.nextInt();
                arr[i][j] = sum;
            }
        }

        int K = tokenizer.nextInt();
        StringJoiner sj = new StringJoiner(System.lineSeparator());
        for(int k = 0; k < K; k++) {
            int i = tokenizer.nextInt();
            int j = tokenizer.nextInt();
            int x = tokenizer.nextInt();
            int y = tokenizer.nextInt();
            int acc = 0;
            for(int r = i; r <= x; r++) {
                acc += arr[r][y] - arr[r][j - 1];
            }
            sj.add(String.valueOf(acc));
        }
        System.out.println(sj);
    }

    public static class Tokenizer {
        private BufferedReader br;
        private StringTokenizer st;

        public Tokenizer(BufferedReader br) {
            this.br = br;
        }

        public int nextInt() throws IOException {
            if(st == null || !st.hasMoreTokens()) {
                this.st = new StringTokenizer(br.readLine());
                return nextInt();
            }
            return Integer.parseInt(st.nextToken());
        }
    }
}