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

#include <iostream>
using namespace std;

int DP[100'0001];

int main()
{
	//1. Get input
	ios::sync_with_stdio(0), cin.tie(0);
	int N, M; cin >> N >> M;
	cin >> DP[1];

	int temp;
	for (int i = 2; i <= N; ++i)
	{
		cin >> temp;
		DP[i] = DP[i - 1] + temp;
	}

	//2. Do loop [ O(N) ]
	int a, b;
	for (int i = 1; i <= M; ++i)
	{
		cin >> a >> b;
		cout << DP[b] - DP[a - 1] << "\n";
	}
	return 0;
}

---

||사고 과정

아~~ 뭔가 아쉽게 풀이를 하지 못했다.

 

이미 DP로 푸는 문제인건 알았지만 여러 방식으로 생각하려 했었고

어떠한 숫자들의 합을 미리 구해놓고 이를 이용하는거 까지는 대략 유추했는데

정확한 풀이 까지 가지 못했다.ㅠㅠ

---

||사용 기법

• DP
• Prefix sum

---

||풀면서 느낀 것

• DP면 테이블을 확실히 해볼 것

이번 문제는 테이블에 어떤 값을 넣는지만 알면 굉장히 쉽게 풀수 있었다.

다음에 DP로 풀게되면 테이블에 어떤것을 넣을것인가를 중점으로 생각해봐야겠다.

---

||새로 알게 된것

• Prefix sum

부분합의 알고리즘의 하나인데 이번에 처음 알게 됐다.

0 ~ N 까지  각 i번째에 이전 수들의 합을 모두 저장해놓는다.

 

그 후 i ~ j 까지의 합을 구하려면

arr[ j ] - arr[ i - 1 ] 로 O(1)에 구해버릴 수 있다.ㄷㄷ

완전 신기함ㅋㅋㅋ

---

||나아 진것

• 그래도 어느정도 DP를 핥고 맛을 느낄 줄 알게 된듯하다.