[C++] 11660번 구간 합 구하기 5 - DP, 누적 합

#include <iostream>

#define MAX_SIZE 1025

using namespace std;

int N, M;  //표의 크기 N, 합을 구해야 하는 횟수 M
int x1, y1, x2, y2;
int memo[MAX_SIZE][MAX_SIZE];  //메모리제이션 누적합
int map[MAX_SIZE][MAX_SIZE];  //맵

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for(int i=1; i<=N; i++) {
        int sum=0;
        for(int j=1; j<=N; j++) {
            cin >> map[i][j];
            sum+=map[i][j];
            memo[i][j] = memo[i-1][j]+sum;  //(0, 0)에서 (x, y)까지의 누적합
        }
    }
    
    for(int i=0; i<M; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        
        cout << memo[x2][y2]-memo[x2][y1-1]-memo[x1-1][y2]+memo[x1-1][y1-1] << '\n';
    }
    
    return 0;
}

 

생각해보니까 맨 처음에 메모저장할 때도 굳이 map을 쓸 필요가 없었던 것 같다. map을 쓰지 않고 (x1, y1)에서 (x2, y2)의 합 구하는 것 처럼 (0, 0)에서 (x1, y1)까지의 합을 구하면 더 빨리 나왓을 것 같은데. 아 그리고 새로 알게된 점은 endl은 느려서 쓰면 안된다는 것이었다. 이것때문에 시간 초과가 났었던 것이라고 한다.ㅋㅋㅋㅋ 참고한 사이트는 아래에 있다. 누적합은 처음 보는 거라서

 

<누적 합>

https://jow1025.tistory.com/47

누적합(prefix sum)

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다