알고리즘 문제/다이나믹 프로그래밍
[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);
}
}