백준 11659번 구간 합 구하기 4

< 백준 11659번 구간 합 구하기 4 - 마포 코딩박 >

사용한 알고리즘: Prefix Sum ( 구간합 배열 )


 구간합 배열을 구해 출력하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 8~12)
  'pSum[x] : 1~x 구간의 합' 이라고 설정하였습니다.
 입력을 받음과 동시에 구간합을 구합니다. 'pSum[x] = pSum[x-1]+x성분값' 입니다.

(2) (코드 13~18)
 s~e 성분합 = pSum[e] - pSum[s-1] 입니다. 이를 사용하여 M개의 입력으로 주어지는 i~j 구간합을 출력합니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N, M, pSum[100001];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	// 입력받으면서 prefix sum을 채움(1칸이 더 필요함에 유의)
	cin >> N >> M;
	for(int i = 0; i < N; ++i){
	int A;
	cin >> A;
	pSum[i+1] = pSum[i] + A;
	}
	// s~e 성분 합 = pSum[e] - pSum[s-1]
	for(int i = 0; i < M; ++i){
	int s, e;
	cin >> s >> e;
	cout << pSum[e]-pSum[s-1] << '\n';
	}
	}

view raw BOJ 11659.cpp hosted with ❤ by GitHub