이번에 풀어본 문제는
백준 15724번 주지수 입니다.

📕 문제 링크

❗️코드

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

public class Main{
    static int [][] map;
    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][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()) + map[i-1][j] + map[i][j-1] - map[i-1][j-1];
            }
        }

        int K = Integer.parseInt(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < K; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int res = map[x2][y2] - map[x2][y1-1] - map[x1-1][y2] + map[x1-1][y1-1];
            bw.write(res+"\n");
        }

        bw.flush();
        bw.close();
    }
}

📝 풀이

왕이 궁금해하는 K개의 범위에 대한 결괏값을 출력하는 문제입니다.
dp로 풀었지만, dp배열이 따로 필요하진 않을 것 같아서 map을 그대로 활용했습니다.
map[i][j]의 값은 map[1][1]부터 map[i][j]까지의 합을 의미합니다.
따라서 값을 입력받음과 동시에 입력된 값 + map[i-1][j] + map[i][j-1] - map[i-1][j-1] 연산을 해주면, 현재 입력받은 위치 까지의 값을 누적하여 더하면서 진행할 수 있습니다. 그림으로 생각해보면 쉽게 이해할 수 있습니다.
위 과정으로 map을 설정 해주면, K개의 입력에 대한 값은 map 배열을 활용해 쉽게 구해낼 수 있습니다.

📜 후기

왠지 비슷한 문제를 풀어본 기억이 있어서, 쉽게 접근할 수 있었습니다.