[BOJ] 구간 합 구하기 5

구간 합 구하기 5

TimeLimit	MemoryLimit	Condition	TAG
1s	256MB	(1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)	Dynamic Programming, 구간합

이번 문제는 그냥 구간합 구하는 문제로 처음보는 분들은 연습하기 좋은 문제인 것 같습니다.

그냥 지나오면서 다 더하고, 나중에 전에 값을 빼서 값을 알아오는 방법으로 값을 얻을 수 있습니다. Indexing을 사용하면 속도가 빠르기 때문에 아주 많이 사용되더라구요.

한번 연습해보시면 좋을 듯 합니다.

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;
int board[1025][1025];
int n, m;



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>> n >> m;
    
    board[1][0] = 0;
    for(int i = 1; i <= n; i++){
        cin >> board[1][i];
        if(i) board[1][i] += board[1][i-1];
    }
    for(int i = 2; i <= n; i++){
        board[i][0] = board[i-1][n];
        for(int j = 1; j <= n; j++){
            cin >> board[i][j];
            board[i][j] += board[i][j-1];
        }
    }
    
    
    int x1, y1, x2, y2;
    while(m-->0){
        
        cin >> x1 >> y1 >> x2 >> y2;
        
        ll result = 0;
        for(int x = x1; x <= x2; x++)
            result += board[x][y2] - board[x][y1-1];
        
        cout << result << "\n";
    }
    
    return 0;
}