백준 11660번 시간초과 (java)

접근

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

일단 이 문제는 시간제한이 1초이기 때문에 시간초과가 발생하지 않도록 주의해서 풀어야 한다.

나름 줄인다고 줄였는데 4번의 시도 끝에 결국 풀지 못했다.

나의 접근방법은
2중 for문을 돌지 않기 위해서 값들을 배열로 저장하지 않고 list에 저장했고 list의 index로 접근하기 위해 아래와 같이 for문을 만들었다.

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

            int answer=0;
            for(int j=(x1-1)*N ; j<=N*x2-1;j++){
               if(j%N>=y1-1 && j%N<=y2-1){
                   answer+=list.get(j);
               }
            }
            bw.write(Integer.toString(answer)+"\n");
        }

보면 시간복잡도가 최대 100,000(M)X1024(N)X1024(N)이 온다.

list에 저장하지 않았지만 결국 계산할 때 MXN^2이다.
잘못된 풀이라는 것을 깨달았다.

결국 다른 분의 풀이를 통해서 DP를 통해 접근해야 한다는 것을 알았다.

왜 DP를 떠올리지 못했을까
동빈북을 구입하는 계기가 되었다..

과정

DP를 통해서 행별 누적합을 만든다.

위 문제의 예시를 통해서 만들어본 행별 누적합은 위와 같다.

(2,2) 부터 (3,4)까지의 합은 dp[2][4] - dp[2][1] + dp[3][4]-dp[3][1]이다.

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

            int answer =0;
            for(int j=x1;j<=x2;j++){
                answer += dp[j][y2] - dp[j][y1-1] ;
            }
            bw.write(Integer.toString(answer)+"\n");
        }

DP로 접근하면 위와 같이 최대 100,000(M) X 1024(N)으로 시간복잡도가 MXN임을 확인할 수 있다.

풀이(java)

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


public class Main{

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

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

            int answer =0;
            for(int j=x1;j<=x2;j++){
                answer += dp[j][y2] - dp[j][y1-1] ;
            }
            bw.write(Integer.toString(answer)+"\n");
        }



        bw.flush();
        bw.close();
        br.close();



    }


}