(백준/c++) 11660 - 구간 합 구하기 5

핑크코냥 2022. 6. 23. 18:08

728x90

11660번: 구간 합 구하기 5

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네

www.acmicpc.net

다이나믹 프로그래밍

1. "11659 - 구간 합 구하기4"를 2차원으로 변형한 문제라고 접근했다.

2. 동일한 크기의 행렬을 하나 더 만들어 입력을 받는 동시에 이전의 합과 현재값을 더하여 index 1 ~ index 현재까지의 합을 구해주었다.

3. begin : (x1, y1) end: (x2, y2) 로 구분하여 end부터 begin까지의 합을 구해주었다.

	#include<iostream>
	#include<stdlib.h>
	#include<memory.h>
	using namespace std;
	#define MAX 1025
	int SumArr[MAX][MAX], Arr[MAX][MAX];


	int main(void)
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(SumArr, 0 , sizeof(SumArr));
	memset(SumArr, 0 , sizeof(SumArr));

	int N, M; // N: 표의 크기 M: 횟수 (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)
	cin >> N >> M;

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

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

	for(int i=0; i<=(x2 - x1) ; ++i)
	{
	result += (SumArr[x2-i][y2] - SumArr[x2-i][y1-1]);

	}
	cout << result <<"\n";
	}


	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

동적 계획법은 Bottom-Up, Top-Down등 다양한 해답이 많으니 참고만 해주면 좋겠습니다..

728x90