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

유형	난이도	완료일	링크	특이사항
DP	실버1	23.4.5	https://www.acmicpc.net/problem/11660

 

 

내 코드

#include <iostream>

using namespace std;

int x1,x2,y1,y2;
int n, m;
int arr[1025][1025];
int dp[1025][1025];
int sum = 0;

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	cin >> n >> m;
	
	for(int i=1; i<=n; i++)
	{
		for(int j= 1; j<=n; j++)
		{
			cin >> arr[i][j];
		}
	}
	
	
	
	for(int i=1; i<=n; i++)
	{
		dp[i][1] = arr[i][1];
		
		for(int j = 2; j<=n; j++)
			dp[i][j] = dp[i][j-1] + arr[i][j];	
	}
	
	for(int i=0; i<m; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2; //x는 행 y는 열
	
		for(int i = x1; i<=x2; i++)
		{
			 sum += dp[i][y2] - dp[i][y1-1];
		}
	
		cout << sum << "\\n";
		sum = 0;
	}
}

2차원 배열의 구간합을 구하는 문제다. 최대 1024 * 1024 배열에 포함되는 랜덤한 모양의 구간합을 구해야 해서 DP로도 구해야 하는 경우의 수가 너무 많다고 생각했다 n-1과 n의 연관성을 찾으려 해도 배열에 포함 가능한 경우의 수가 너무 많아 무엇이 n-1이고 무엇이 n인지 정할 수도 없었다.

그래서 전에 풀었던 이전 문제 - 구간 합 구하기 4 문제를 참고했다. 해당 문제는 1차원으로 주어지는 숫자들의 구간 합을 구하는 문제였다. 이 문제를 보고 다시 2차원 배열에서 문제를 어떻게 해결할까 생각해보니 1차원에서 구간 합을 구하는 것을 n번 더 반복하면 그게 2차원 배열에서의 구간 합이라는 생각을 할 수 있었다.

dp[i][j]에는 i번째 행의 1부터 j까지의 합을 저장한다. 이후 배열의 두 지점을 입력받으면 해당 배열의 x1행 부터 x2행까지 1차원 구간 합을 구하듯 (1~j번째까지의 합) - (1~i-1번째 까지의 합)을 각 행마다 구해서 모두 합한다.

다른 코드

#include <iostream>

using namespace std;

int arr[1025][1025],dp[1025][1025];

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

    int n,m;
    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;
    int ans;
    for(int i=0;i<m;i++) {="" cin="">>x1>>y1;
        cin>>x2>>y2;
        ans = dp[x2][y2] - dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
        cout<<ans<<'\n';
    }
    return 0;
}
//https://donggoolosori.github.io/2020/10/13/boj-11660/

dp 배열을 내 코드와 다른 방식으로 만들었다. dp[i][j]에 dp[1][1]~dp[i][j]까지의 합을 담는다. 이 과정에서 dp[i-1][j-1]영역이 두 번 더해지므로 한 번 빼준다. 이렇게 만든 dp를 기반으로 dp를 만들었던 방식과 비슷하게 답을 구할 수 있다. dp[x2][y2]에서 불필요한 값들을 빼주는 방식이다.