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

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

 

풀이1

우선 누적합을 이용해 2차원 배열에 값을 채워넣는다

(배열의 (i, j)에는 (0, 0)부터 (i, j)번째까지의 모든 값이 담긴다. 즉, (i + 1, 0) 위치에는 (i, n)까지의 합에 (i + 1, 0) 번째 수가 더해진 값이 들어가게 된다)

답은 각 행의 x2의 누적합 - x1의 누적합을 행의 갯수만큼 반복하여 더해주면 된다

위 배열이 주어졌다고 가정했을 때, 누적합을 이용해 배열을 채우면 아래와 같다

제출 코드

#include <iostream>
using namespace std;

int ps[1025][1025];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, input;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> input;
            ps[i][j] = ps[i][j - 1] + input;
        }
        if (i != n) ps[i + 1][0] = ps[i][n];
    }

    while(m--)
    {
        int sum = 0;
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        
        for (int i = a; i <= c; i++)
            sum += ps[i][d] - ps[i][b - 1];
        
        cout << sum << '\n';
    }
}

 

 

풀이 2 (DP)

2차원 배열에 넣는 값은 (0, 0)부터 (x, y)까지 직사각형을 그려 그 안에 들어가는 모든 값의 합이다 (풀이 1에서 앞선 모든 값을 누적시킨 것과 다름)

위 원리를 이용해 2차원 배열의 값을 채워준다

 

답을 구하는 원리는 위와 같다

전체 큰 박스에서 초록색으로 표시된 양쪽 박스의 값을 빼고, 겹쳐서 2번 빼버린 구간의 값을 한 번 더해준다

(모든 값은 배열에 한번 접근하는 것으로 구할 수 있다)

 

제출 코드

#include <iostream>
using namespace std;

int dp[1025][1025];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, input;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> input;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + input;
        }
    }

    while(m--)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << '\n';
    }
}

참고) 위 방식을 적용시키기 위해 0번째의 행과 열은 전부 0인 상태로 놔두어야 범위 밖 인덱스에 접근하는 일이 생기지 않는다