백준 11660 구간 합 구하기 5 c++ [컴공과고씨]

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

11660번: 구간 합 구하기 5

 

문제 정리

1. 행렬이 주어짐.

2. 시작 좌표 (x1,y1)이 주어지고 도착 좌표 (x2,y2)가 주어짐

3. 좌표 사이에 있는 값의 합들을 구해야함.

예를 들어 초록색이 시작 좌표, 파란색이 끝 좌표라고 하면 저런식으로 보라색 빗금의 부분의 합들을 구해주면됨.

 

문제 해결 방법

그 전 구간 합 구하기를 해보면 알듯이 일일이 for문을 돌리면서 구해주면 시간 초과가 난다.

그래서 다이나믹 프로그래밍을 이용해 풀어주어야 한다.

일단 나는 map[i][j]의 배열의 의미를 정의를 어떻게 했냐면

(1,1) 부터 (i,j)의 구간의 합으로 정의를 해주었다.

이런식으로 보라색 좌표의 값은 빨간색의 합을 구한 것으로 정의하는 것이다.

 

그럼 저 것을 어떻게 구해나가면 되냐?

이런식으로 가면됩니다. 

1번 부분은 map[i-1][j] 이고

2번 부분은 map[i][j-1] 입니다.

그리고 겹쳐지는 노란색 3번 부분은 map[i-1][j-1]이 되죠?

그럼 1번과 2번을 더해서 3번 부분을 빼주고 (i,j)좌표 칸의 값을 더해주면 map[i][j]의 값이 됩니다.

 

그럼 똑같이 x1,y1에서 x2,y2까지 합을 구하려면?

st이 x1, y1

dt가 x2,y2라고 하면 

map[x2][y2](빨강) - map[x1-1][y2](파란) - map[x2][y1-1](초록) + map[x1-1][y1-1](갈색)

이 사이 구간의 합이 된다.

 

전체코드

#include <iostream>
 
using namespace std;
int map[1206][1206] = {0}; // i,j까지 합
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >>  m;
    int temp;
    
    for (int i = 1; i <= n; i++){
        int sum = 0;
        for (int j = 1; j <= n;j++){
            cin >> temp;
            map[i][j] = map[i - 1][j] + map[i][j - 1] + temp - map[i - 1][j - 1];  // i,j 까지 합 구하기
        }
    }
 
    int x1, y1, x2, y2;
    
    for (int i = 0; i < m;i++){
        int result = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        result = map[x2][y2] - map[x1 - 1][y2] - map[x2][y1 - 1] + map[x1 - 1][y1 - 1];  // 사이 구간 합
        cout << result << '\n';
    }
 
    return 0;
}