[Algorithm] 백준_구간 합 구하기 5_11660번 (JAVA)

📝문제

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

구간 합 구하기 5 : 11660번

티어 : 실버 1

 

💡풀이

문제 유형

다이나믹 프로그래밍

 

걸린 시간

80분..

 

시간 복잡도

 

 

풀이 방법 도출

1. 전에 비슷한 문제를 풀었어서 어렴풋한 기억을 가지고 풀었다.
2. 일단 arr 배열에 입력 받은 값들을 넣어주고
3. dp 배열을 생성한다. dp[i][j] = (1,1) 부터 (i,j)까지의 합
4. 이때 dp[i][j] = arr[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; 의 규칙을 갖는다.
5. dp배열을 완성하면 (x1,y1)에서 (x2,y2)까지의 합을 구할 준비가 되었따.
6. 구간 합 식은 다음과 같다. sum = dp[x2][y2] - (dp[x1 - 1][y2] + dp[x2][y1 - 1] - dp[x1 - 1][y1 - 1]);

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

class Main {
    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());

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

        int[][] dp = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = arr[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            int sum = 0;
            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());

            sum = dp[x2][y2] - (dp[x1 - 1][y2] + dp[x2][y1 - 1] - dp[x1 - 1][y1 - 1]);

            sb.append(sum).append("\n");
        }

        System.out.println(sb);
    }
}

 

🤔Review

규칙을 찾고 식을 생성하는데 너무 헷갈려서 시간이 오래 걸렸다. 헷갈려 너무너무