오늘도 매일코딩 저장소에서 1-4까지 랜덤 수를 뽑아서 문제를 풀었다 ! 오늘의 랜덤 숫자는 2번 !
그래서 오늘 푼 문제는 백준 11660 - 구간 합 구하기 5 이다.
문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
예제
입력 1
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4출력 1
27
6
64입력 2
2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2출력 2
1
2
3
4풀이 방법
문제 1번의 예시를 가지고 살펴보면,
구해야 하는 값은 노란 영역의 값인데, 이 값은 아래와 같이 구할 수 있다.
노란 영역의 합 = 초록 영역의 합 - 연보라 영역의 합 - 진보라 영역의 합 + 빨간 동그라미 영역의 합 (1)
// dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1];즉, 값을 구하기 위해서 (1,1)부터 (i,j) 까지 영역의 총 합들이 계속 사용이 되는 것을 알 수 있다 !
그러므로 새로운 N*N 배열( dp배열이라고 부르겠다 ! )에 (i,j)에 (1,1)부터 (i,j) 까지 영역의 총 합을 저장해두면 바로바로 가져다가 계산만 해서 원하는 값을 얻을 수 있게 되는 것이다 !
( 이런 접근을 하기 전에 단순 반복문의 시작, 종료 조건만을 조정해줄 수도 있지만 입력값의 범위가 크고, M개의 케이스에 대한 값을 구해야 하기 때문에 반복되는 계산을 줄이는 것이 필요하다고 생각해서 dp를 떠올렸다 ! )
또한 보드를 한 번 쭉 탐색하며 dp를 채워 나갈 때, dp[i][j]를 구하는 데에 이전에 구해둔 dp 값들이 사용되기 때문에 dp라는 것을 더 확신할 수 있다 !
즉 위의 그림에서 dp[3][3] 즉 노란 영역의 합은 아래와 같이 구할 수 있다.
노란 영역의 합 = 보라 영역의 합 + 초록 영역의 합 - 빨간 영역의 합 + 현재 좌표의 보드 값 (2)
// dp[i][j] = dp[i-1][j] + dp[i][j-1] + board[i][j] - dp[i-1][j-1];이 때, 이미 보라 영역의 합, 초록 영역의 합, 빨간 영역의 합은 구해져있으며, 현재 좌표의 보드 값도 바로 받아올 수 있다는 것이다 !
또한 위와 같이 dp를 채워나갈 때, (1,1)부터 일관된 식으로 채우기 위해서 아래와 같이 0행 0열을 0으로 모두 초기화 시켜주는 과정을 넣어주었다 !
정리하면 (2)번 식대로 dp를 초기화해주고, (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)); // reader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
StringTokenizer st; // tokenizer
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] board = 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++){
board[i][j] = Integer.parseInt(st.nextToken());
}
}
// 초기값
int[][] dp = new int[n+1][n+1];
dp[0][0] = 0;
for(int i=1; i<=n; i++){
dp[0][i] = 0;
dp[i][0] = 0;
}
// init dp
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1] + board[i][j] - dp[i-1][j-1];
}
}
int x1, y1, x2, y2, result;
for(int i=0; i<m; i++){
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken())-1;
y1 = Integer.parseInt(st.nextToken())-1;
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
result = dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1];
bw.write(result+"\n");
}
bw.flush(); // flush
bw.close(); // close
br.close(); // close
}
}