[백준]_11659번_구간 합 구하기 [C++]

 

구간 합 구하기 4 성공

 

1 초

256 MB

70324

29504

22430

40.163%

문제

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

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 1 복사

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 복사

12
9
1

---

풀이

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false); // 시간 단축을 위한 
	//입출력 속도를 높이기 위함(버퍼를 지우는 작업이 줄어듬)
	cin.tie(NULL); 
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	int S[100000] = {};

	for (int i = 1; i <= N; i++)
	{
		int temp;
		cin >> temp;
		S[i] = S[i - 1] + temp; // 구간 합 구하기
	}

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

• 다음으로, N과 M을 입력 받고, S 배열을 초기화합니다. 그리고 for문을 사용하여 N개의 수를 입력 받아 S 배열에 저장하고, 각 원소들의 누적 합을 계산합니다. 이렇게 계산된 S 배열은 구간 합을 계산하는 데 사용됩니다.따라서, 이 코드는 입력된 배열의 각 구간의 합을 빠르게 계산하여 출력하는 코드입니다.
  • ios::sync_with_stdio(false); : 입력과 출력의 속도를 높이기 위해 사용하는 코드입니다.
  • cin.tie(NULL); : cin과 cout을 끊어서 사용함으로써 버퍼를 비우는 작업을 줄입니다. 입력을 받을 때마다 버퍼를 비우는 작업이 없어져서 입력 속도를 높일 수 있습니다.
  • cout.tie(NULL); : 마찬가지로 cout을 cin과 끊어서 사용함으로써 출력 속도를 높일 수 있습니다.
  • int N, M; cin >> N >> M; : 입력으로 N과 M을 받습니다.
  • int S[100001] = {}; : S 배열을 초기화합니다. S[i]는 배열 A의 1번째 원소부터 i번째 원소까지의 합을 저장합니다.
  • for (int i = 1; i <= N; i++) { ... } : for문을 사용하여 N개의 수를 입력 받고, S 배열을 계산합니다. S[i] = S[i-1] + A[i]를 이용하여 S 배열을 계산합니다.
  • for (int i = 0; i < M; i++) { ... } : M개의 구간을 입력 받아서, 각 구간의 합을 출력합니다. 이때, 각 구간의 합은 S 배열의 누적 합을 이용하여 S[end] - S[start-1]로 계산됩니다.
  • cout << S[end] - S[start - 1] << "\\n"; : 각 구간의 합을 출력합니다.
• 마지막으로, M개의 구간을 입력 받아서, 각 구간의 합을 출력합니다. 이때, 각 구간의 합은 S 배열의 누적 합을 이용하여 S[end] - S[start-1]로 계산됩니다.
• cin과 cout의 입출력 속도를 높이기 위해 ios::sync_with_stdio(false)를 사용하고, 입출력 속도를 높이기 위해 cin.tie(NULL)와 cout.tie(NULL)을 사용합니다.