[백준] 11660번 구간 합 구하기 5

이거.... 이거 어떻게 풀지...?

문제를 처음 본 순간 뇌정지가 왔다...

 

자자 정신차리고

이 문제는 2차원 배열의 구간 합을 구하는 문제다.

 

원본 배열 arr과 합친 누적합 배열sum이 있다고 생각하고 진행하겠다.

 

처음에 입력받는 값이 N 그리고 M이다.

N * N 짜리의 테이블을 생성한다고 생각하자

음! 그러면 이중 for문을 사용하는데 다 N까지라고 생각하면 되겠구나!

1. 값을 입력받는다.

2. 원본 배열 안에 값을 넣는다. (이중 for문)

3. 누적합 배열을 구한다.

4. 구간합을 구한다.

 

누적합 배열을 구하는 방법은!

sum[i][j] = sum[i][j - 1] - sum[i - 1][j] - sum[i - 1][j - 1] + arr[i][j]

 

구간합 배열을 구하는 방법은!

int result = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];

 

 

가장 쉬운 방법은 입력값대로 표를 만들어보고 이에 맞춰서 중복되는 부분들은 제외하고 그리고 두 번 없어지는 부분들은 더한다.