백준 11659번 구간 합 구하기

https://www.acmicpc.net/problem/11659

 

아이디어:

1. 현재 인덱스 까지의 총 합을 구하는 배열 int S[] 생성

2. S[i] = S[i - 1] + A[n] (ex A: 1 2 3 4 5, S: 1 3 6 10 15)

3. 구간 i ~ j 까지의 합은 S[j] - S[i - 1]과 동일

4. 문제의 인덱스에 맞춰 배열의 크기는 S[100001], 순회는 (int i = 1, i <= N, i++)

5. S[0] 은 0으로 두고 S[1]부터 A[1] 과 동기화

// 11659

#include <iostream>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, i, j;
	int A[100001] = { 0 };
	int S[100001] = { 0 };

	cin >> N >> M;

	for (int n = 1; n <= N; n++) {
		
		cin >> A[n];
		S[n] = S[n - 1] + A[n];

	}
		
	for (int n = 0; n < M; n++) {
		
		cin >> i >> j;
		cout << S[j] - S[i - 1] << "\n";

	}

	return 0;

}

 

모범답안:

1. 기존 입력받는 배열 A[]는 제외하고 S[]만 사용해도 문제 풀이 가능

2. int temp, S[i] = S[i - 1] + temp

 

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, i, j, tmp;
	int S[100001] = { 0 };

	cin >> N >> M;

	for (int n = 1; n <= N; n++) {

		cin >> tmp;
		S[n] = S[n - 1] + tmp;

	}

	for (int n = 0; n < M; n++) {

		cin >> i >> j;
		cout << S[j] - S[i - 1] << "\n";

	}

	return 0;

}