[C++]구간 합 구하기 4 - 백준11659

문제

• 구간 합 구하기 4(백준11659)

풀이

문제 해석을 하자면,

• 주어진 구간의 합을 구하는 문제

풀이

• 문제 제한을 보면 시간제한을 조심해야 하므로 DP로 풀이
• 규칙이 쉬워서 bottom-top으로 쉽게 풀 수 있다.
• 방법은 구간합을 전부 구해놓고 활용 하기만 하면 된다.
• 입출력이 많으므로 시간초과 뜰 수 있으니 꼭 ios::… cout.tie(0)까지 선언

코드

#include<iostream>

using namespace std;

int N, M;

long long dpArr[100005];

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

	int inNum = 0;
	cin >> N >> M;
	cin >> inNum;
	dpArr[1] = inNum;
	for (int i = 2; i <= N; i++) {
		cin >> inNum;
		dpArr[i] = dpArr[i - 1] + inNum;
	}

	int inNum1 = 0; int inNum2 = 0;
	for (int i = 0; i < M; i++) {
		cin >> inNum1 >> inNum2;
		cout << dpArr[inNum2] - dpArr[inNum1 - 1]<<'\n';
	}

	return 0;
}

느낀점

생략