[백준] 🥈 11660 구간 합 구하기 5

📌 난이도

🥈 Silver 1

📌 문제

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

📌 풀이

이 문제를 처음 봤을때, 어떻게 해야할지 바로 감이 잡히지는 않았다.
그래서 이전에 풀어본 누적합 문제들을 떠올리며 찬찬히 고민해 보았다.
결국 모든 누적합 문제들은 이전까지의 숫자들을 더한 누적합 배열이 있어야하고, 그 누적합 배열에 어떤 값이 들어가는지가 가장 중요하다.

그래서 누적합 배열에는 이전 좌표값까지의 모든 값을 더한 후, 넣기로 하였다.

그리고 계산을 할때는 현재 (x2, y2)값에서 (x1 - 1, y2)와 (x2, y1 - 1)을 빼고 (x1 - 1, y1 - 1)를 더해주었다.

그러자 다음 코드와 같이 성공적으로 구현이 되었다.

📌 Code

package PS;

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

public class N11660 {
    static int[][] numbers;

    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());

        numbers = new int[N + 1][N + 1];

        for (int i = 0; i <= N; i++) {
            numbers[i][0] = 0;
            numbers[0][i] = 0;
        }
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                MakePrefixSum(i, j, Integer.parseInt(st.nextToken()));
            }
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            PrefixSum(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
    }

    static void MakePrefixSum(int x, int y, int value) {
        numbers[x][y] = numbers[x][y - 1] + numbers[x - 1][y] - numbers[x - 1][y - 1] + value;
    }

    static void PrefixSum(int x2, int y2, int x1, int y1) {
        int result = numbers[x1][y1] - numbers[x2 - 1][y1] - numbers[x1][y2 - 1] + numbers[x2 - 1][y2 - 1];
        System.out.println(result);
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁