이번에 풀어본 문제는
백준 11660번 구간 합 구하기 5 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int [][] map;
    static int [][] dp;
    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());

        map = new int[n+1][n+1];
        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)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] + map[i][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int start_x = Integer.parseInt(st.nextToken());
            int start_y = Integer.parseInt(st.nextToken());
            int end_x = Integer.parseInt(st.nextToken());
            int end_y = Integer.parseInt(st.nextToken());

            int res = dp[end_x][end_y] - dp[end_x][start_y-1] - dp[start_x-1][end_y] + dp[start_x-1][start_y-1];
            sb.append(res).append("\n");
        }
        System.out.print(sb.toString());
    }
}

📝 풀이

dp문제입니다.
dp[i][j]에는 (0,0) 부터 (i,j)까지의 총 합이 들어가게 되며 저장된 누적 합을 활용해
주어진 인덱스사이 값들의 합을 구할 수 있습니다.

📜 후기

이번 2022 카카오 코딩테스트에서 효율성을 통과하지 못한 비슷한 문제가 있었는데,
그점을 보완하고자 누적합 문제를 풀어보고 있습니다. 비슷하지만 다른 것 같아 좀 더 다양한 문제들을 풀어볼 생각입니다.