[백준] 구간 합 구하기 5 11660 java - dp

 

 

N과 M의 범위 때문에 값을 일일이 구하면 시간초과가 발생한다

따라서 dp를 이용해서 풀어야 한다는 것은 이해가 갔는데..

일반적인 누적합을 이용하니 결과를 구할때에 N*M 시간복잡도가 나와

아슬아슬하게 테케를 통과했다...

출처: https://developerjisu.tistory.com/9

위의 사진처럼 누적합을 구해야한다는 것을 깨달았다!

1. 1행/1열은 단순 누적합

ex. 1행이 1 2 3 4 -> 1 3 6 10

1열이 1 2 3 4 -> 1 3 6 10

2. 나머지 행/열부터는 위와 같은 방식으로 누적합을 구해야지

표에 한번에 저장할 수 있다

 

 

[1차 풀이]

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

public 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[][] graph = new int[N + 1][N + 1];
        int[][] 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++) {
                int value = Integer.parseInt(st.nextToken());
                graph[i][j] = value;
                if (j == 1) {
                    dp[i][j] = value;
                } else {
                    dp[i][j] = dp[i][j - 1] + value;
                }
            }
        }

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < M; 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());
                if (x1 == x2 && y1 == y2) {
                    sb.append(graph[x1][y2] + "\n");
                } else {
                    int result = 0;

                    for(int j=x1;j<=x2;j++)
                        result+=dp[j][y2]-dp[j][y1-1];
                    sb.append(result + "\n");
                }
            }

            System.out.println(sb);

    }
}

 

 

[정답]

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

public 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[][] graph = new int[N + 1][N + 1];
        int[][] 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++) {
                int value = Integer.parseInt(st.nextToken());
                graph[i][j] = value;
                //첫번째 행과 첫번째 열은 해당 값 저장
                if(i==1) {
                    dp[i][j] = dp[i][j-1]+value;
                }
                else if (j == 1) {
                    dp[i][j] = dp[i-1][j]+value;
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i-1][j]+value-dp[i-1][j-1];
                }
            }
        }

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < M; 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());
                if (x1 == x2 && y1 == y2) {
                    sb.append(graph[x1][y2] + "\n");
                } else {
                    int result = dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
                    sb.append(result + "\n");
                }
            }

            System.out.println(sb);

    }
}