알고리즘 문제/다이나믹 프로그래밍

[Java] 다이나믹 프로그래밍 누적 합 (구간 합 구하기5)

안도일 2023. 2. 1. 00:23

알고리즘은 맞았지만 생각지도 못한 이유로 시간초과에 걸려서 고생한 문제다.

다이나믹 프로그래밍을 이용해 누적합을 저장하는 dp 테이블을 생성하고 그 테이블을 이용해 Time Complexity를 줄이는 문제.

 

처음 문제를 보고 익숙한 누적 합 문제라 바로 dp 테이블을 만들고 문제를 풀었는데 아뿔싸 시간초과가 났다.

 

 

내가 푼 방식은 dp 테이블을 열 기준으로 한 줄씩 생성하는 것이다. 

 

 

아무리 머리를 굴려도 내가 푼 방식보다 더 빠르게 동작하는 방법이 생각나지 않아 해답을 찾아봤는데 나랑 알고리즘이 똑같았다.  다른 점이 하나 있었는데 나는 반복문이 돌 때마다 System.out.print를 하면서 답을 출력했는데 풀이에는 StringBuilder sb에 답을 저장해 놓고 마지막에 sb를 출력하는 형식이었다. 해당 방식으로 내 코드를 수정하니 시간초과에 걸리지 않았다. System.out.print가 꽤 비싼 연산이라는 것을 알게 되었다. 앞으로 이렇게 출력이 많을 때는 StringBuilder에 저장해 놓고 한 번에 출력하자.

 

 

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

 

11660번: 구간 합 구하기 5

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네

www.acmicpc.net

 

 

 

 

public class Main {

    static int N,M; //NxN 행렬
    static int[][] dp; //누적합
    static int x1, y1, x2, y2, sum;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dp = new int[N+1][N+1];

        for(int i=1; i<N+1; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<N+1; j++){
                dp[i][j] = dp[i][j-1] + Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            x1=Integer.parseInt(st.nextToken());
            y1=Integer.parseInt(st.nextToken());
            x2=Integer.parseInt(st.nextToken());
            y2=Integer.parseInt(st.nextToken());

            sum = 0;

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

        }
        System.out.print(sb);
    }

}