[백준(BOJ)] 11660번 : 구간 합 구하기 5 - C++[CPP]

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

11660번: 구간 합 구하기 5

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍
• 누적 합

 

---

 

⊙ 문제 접근 과정

 

2차원 dp 배열을 만들어주고 누적합을 저장해준다.

 

이 문제에서 누적합을 구할 때, 중복만 제거해주면 된다.

 

+	-
-	result

 

+는 두 번 빼서 한번 더하는 곳이다.

 

dp[i][j] = dp[i-1][j]+dp[i][j-1] - dp[i-1][j-1]+arr[i][j];

 

---

 

⊙ 문제 풀이

 

#include <iostream>

using namespace std;
#define MAX 1025

int arr[MAX][MAX],dp[MAX][MAX];
int N, M;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;

    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            cin >> arr[i][j];
            dp[i][j] = dp[i-1][j]+dp[i][j-1] - dp[i-1][j-1]+arr[i][j];
        }
    }

    int x1,y1,x2,y2, result;

    for(int i=0;i<M;i++) {
        cin >> x1 >> y1;
        cin >> x2 >> y2;

        result = dp[x2][y2] - dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
        cout << result << "\n";
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!