[Boj_2167] 2차원 배열의 합

📎 문제 링크

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

2167번: 2차원 배열의 합

 

▸ 문제

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

 

▸ 입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

 

▸ 출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

 

📍 문제 정보

• 🥈 문제 레벨 : 실버 5
• 🔔  문제 유형 : 구현, 누적 합
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

• 입력으로 주어진 2차원 배열에 대한 누적합을 저장할 배열을 생성한 뒤, 배열에 누적합을 계산하여 저장했다.
  • prefix[i][j] = map[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
• (i, j) 위치부터 (x, y) 위치까지의 누적합을 구하기 위해 점화식을 찾아 해결했다.
  • 점화식 : prefix[x][y] - prefix[i-1][y] - prefix[x][j-1] + prefix[i-1][j-1];
  • 합집합 = 전체 누적합 - 왼쪽 누적합 - 위쪽 누적합 + 교집합 누적합

 

🔍 누적합이란 ?

• 배열의 일부 구간에 대한 합을 빠르게 구할 수 있는 알고리즘
• 배열의 값들이 변하지 않는다면 누적된 합 또한 변동이 없다는 점을 적용한다.
• 미리 구해둔 누적합을 통해 배열 중 특정 구간의 부분합을 쉽게 구할 수 있다.
• 값을 미리 저장해 두는 점이 DP와 유사하다.

 

✔ 최종 코드

메모리 : 26240 KB 
시간 : 276 ms

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 배열의 크기
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] map = new int[n+1][m+1];
        int[][] prefix = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 배열에 누적합 저장하기
                prefix[i][j] = map[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
            }
        }
        
        int k = Integer.parseInt(br.readLine()); // 합을 구할 부분의 개수
        while (k --> 0) {
            st = new StringTokenizer(br.readLine());
            // (i, j) 위치부터 (x, y) 위치
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // ans : (i, j) 위치부터 (x, y) 위치까지의 합
            // 점화식 : 전체 누적합 - 왼쪽 누적합 - 위쪽 누적합 + 교집합 누적합
            int ans = prefix[x][y] - prefix[i-1][y] - prefix[x][j-1] + prefix[i-1][j-1];
            bw.append(ans + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

📍 함께 풀어보면 좋은 백준 문제

• 사과나무
• 체스판 다시 칠하기 2