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

11659번: 구간 합 구하기 4

문제!

---

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

---

이번엔 동적계획법 1 다음 단계인 누적합의 첫번째 문제입니다!

 

문제는 그리 어려운 문제가 아니였습니다. 

약간 누적합은 이럴때 사용할수 있다 라는 느낌?

 

 

 

 

우선 누적합! 이때 까지의 합들을 계속 누적하여 저장하여 사용하는 방법으로

 

1 2 3 4 5

이런식으로 배열이 존재할때

 

누적합 배열로 바꾸면? 

1 3 6 10 15  

 

이런식으로 바뀌게 됩니다. 

 

여기서 2~4 번째까지의 합만 구하고싶다! 하면

2+3+4 = 10 -1

 

3개를 모두더하는것고  dp[4]-dp[1] 이렇게  실행하는것이 같다는 것을 알수있습니다.

 

지금 위는 3개만 봐서 그렇지 2~100000 의 합을 구하라 한다면 당연히 dp[100000]-dp[1] 의 연산이 훨씬 빠를것입니다!

 

 

그럼 바로 시작!

---

코드는 위에서 말했던 그대로 입니다.

#include <iostream>
#include <algorithm>

using namespace std;

int memo[100001] = { 0 };

int main(){
	int N;
	int M;

	cin >> N >> M;
	for (int i = 1; i < N+1; i++) {
		cin >> memo[i];
		memo[i] += memo[i-1];
	}


	int a = 0;
	int b = 0;

	for (int i = 0; i < M;i++) {
		cin >> a >> b;
		cout << memo[b] - memo[a-1] << endl;
	}

}

모든 합을 저장해두고 연산1번에 답이 나오게끔  하지만 위의 코드는 시간초과......

cin,cout 을 써서그런가....

 

 

밑의 코드는 통과 되네요;;

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;

int memo[100001] = { 0 };

int main(){
	int N;
	int M;

	cin >> N >> M;
	for (int i = 1; i < N+1; i++) {
		scanf("%d", &memo[i]);
		memo[i] += memo[i-1];
	}


	int a = 0;
	int b = 0;

	for (int i = 0; i < M;i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", memo[b] - memo[a - 1]);
	}

}

 

 

 

그럼 다음 누적합 문제로 찾아오겠습니다!

 

 

 

---

 

ALL

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;

int memo[100001] = { 0 };

int main(){
	int N;
	int M;

	cin >> N >> M;
	for (int i = 1; i < N+1; i++) {
		scanf("%d", &memo[i]);
		memo[i] += memo[i-1];
	}


	int a = 0;
	int b = 0;

	for (int i = 0; i < M;i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", memo[b] - memo[a - 1]);
	}

}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!