[C++] 백준 11660 - 구간 합 구하기 5

• 문제

• 풀이 과정

• 최종 코드

• 잡담

백준 11660 : 구간 합 구하기 5
난이도 : 실버 1

시간 : 자력 x

 

 

문제

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

11660번: 구간 합 구하기 5

풀이 과정

처음에는 2차원 배열로 하나하나 더해주는 식으로 했지만 시간초과가 발생했다.

그래서 이미 계산한 것은 저장하는 메모이제이션 느낌으로 해보려고 했는데 도저히 감이 잡히질 않았다.

결국 카테고리를 봤고, dp라는 것을 보고 아이디어가 떠올랐다.

 

 

dp[i][j] : (0,0) 부터 (i, j) 까지 더한 합이다.

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

dp[i-1][j-1]를 빼주는 이유는 dp[i][j-1] + dp[i-1][j] 연산을 하면 dp[i-1][j-1]이 2번 더해지기 때문이다.

 

 

특정 구간의 합을 구할 때는 아래와 같은 식으로 풀면 된다.

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

(x2, y2)까지의 구간을 구한 뒤 (x1, y1) 구간부터 (x2, y2) 구간을 제외한 구간을 빼준다.

마지막에 dp[x1-1][y1-1]를 해준 이유는 해당 구간이 2번 뺄셈되기 때문이다.

 

 

최종 코드

#include <iostream>
#include <vector>

#define MAX 1025

using namespace::std;

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

int main(){
    scanf("%d %d", &N, &M);
    for(int i=1; i<=N; i++){
       for(int j=1; j<=N; j++){
            scanf("%d", &b[i][j]);
        }
    }
    
    for(int i=1; i<=N; i++){
       for(int j=1; j<=N; j++){
           dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + b[i][j];
        }
    }
    
    for(int i=0; i<M; i++){
        int x1,x2,y1,y2;
        int result = 0;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
        printf("%d\n", result);
    }
    
}

 

 

 

잡담

dp라고 알았으면 더 빠르게 풀 수 있을텐데,,

dp 나에겐 어려워,,