[백준/C++] 11659 구간 합 구하기 4 (S3)

유형	난이도	완료일	링크	특이사항
DP	실버3	23/03/26	https://www.acmicpc.net/problem/11659

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[100001];

int main(void)
{
	ios::sync_with_stdio(false);  cin.tie(NULL);
		
	int n, m;
	cin >> n >> m ;
	
	int arr[100001] = {};
	
	
	for(int i=1;i<=n;i++)
	{
		cin >> arr[i];
	}
	
	dp[1] = arr[1];
	for(int i=2; i<=n; i++)
	{
		dp[i] = dp[i-1]+arr[i];
	}
	
	int a, b;
	for(int i= 0; i<m; i++)
	{
		cin >> a >> b;
		
		if(a == 1)
		{
			cout << dp[b]<<"\\n";
		}	
			
		else
		{
			cout << dp[b]-dp[a-1]<<"\\n";
		}		
	}
	
}

  처음엔 dp[i][j]형태의 2차원 배열을 만들어 i~j까지의 합을 모두 저장했다. 그러나 100000*100000 배열은 메모리 초과로 실행도 되지 않았고 1차원 배열에 그냥 1번 숫자부터 n번 숫자까지의 합을 저장하기로 했다. 어차피 필요한 부분 합을 그때 그때 계산으로 출력할 수 있었다.

cin/ cout 호출 횟수가 100000만쯤 되면 cin.tie(NULL)을 쓰도록 하자.