Prefix sum(구간합)이란 ?
※ Prefix sum(구간합): 구간 합이란 크기가 N인 배열(A라고 가정)이 주어졌을 때, 같은 크기 N인 배열(주로 P)로 표현한다. 각각의 index 0 <= i < n 의 P[i]는 A[0] + A[1] + … + A[i - 1] + A[i]로 표현할 수 있다.
Input : arr[] = {1, 2, 3, 4, 5}
Output : Prefix_arr[] = {1, 3, 6, 10, 15}
int A[100]; // 입력 받을 배열
int P[100]; // 구간 합을 구할 배열
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]);
// P[0]은 0으로 설정해주고 1부터 n까지는 합을 구해서 P 배열에 넣어준다
P[0] = 0;
for (int i = 1; i <= n; i++)
P[i] = P[i - 1] + A[i];
Prefix sum algorithm examples
1) 백준 11659번 - 구간 합 구하기 4
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;
int A[100005];
int P[100005];
int main()
{
int N, M, k;
scanf("%d %d", &N, &M); // N과 M 입력
for (k = 1; k <= N; k++) {
scanf("%d", &A[k]); // 입력받은 정수를 A배열에 저장
}
P[0] = 0;
for (k = 1; k <= N; k++) {
P[k] = P[k - 1] + A[k]; // P배열에 prefix sum 저장
}
int i, j;
for (k = 1; k <= M; k++) {
scanf("%d %d", &i, &j);
printf("%d\n", P[j] - P[i-1]);
}
return 0;
}
2) Codeforces 1003 C - Intense Heat
https://codeforces.com/problemset/problem/1003/C
Problem - 1003C - Codeforces
codeforces.com
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;
int A[5005];
int P[5005];
int main()
{
int n, k, i, j;
double ans;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
P[0] = 0;
for (int i = 1; i <= n; i++) {
P[i] = P[i - 1] + A[i];
}
ans = 0.0;
for (int j = k; j <= n; j++) {
for (int i = 1; i <= n-j+1; i++) {
ans = max(ans, (double)(P[i + j - 1] - P[i - 1]) / (double)j);
}
}
printf("%lf\n", ans);
return 0;
}
3) Codeforces 466 C - Number of Ways
https://codeforces.com/problemset/problem/466/C
Problem - 466C - Codeforces
codeforces.com
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;
long long A[500005];
long long P[500005];
int main()
{
long long num, total, total3, cnt, cnt1;
scanf("%lld", &num);
for (int i = 1; i <= num; i++) {
scanf("%lld", &A[i]);
}
P[0] = 0;
for (int i = 1; i <= num; i++) {
P[i] = P[i - 1] + A[i];
}
total = P[num];
if (total % 3 != 0) {
cnt = 0;
}
else {
total3 = total / 3;
cnt = 0;
cnt1 = 0;
for (int i = 1; i < num; i++) {
if (P[i] == total3 * 2) {
cnt += cnt1;
}
if (P[i] == total3) {
cnt1++;
}
}
}
printf("%lld\n", cnt);
return 0;
}
4) Codeforces 1285 B - Just Eat It!
https://codeforces.com/problemset/problem/1285/B
Problem - 1285B - Codeforces
codeforces.com
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
long long A[100005];
long long P[100005];
long long M[100005];
int main()
{
long long n, i, j, t, total, MN, ans;
scanf("%lld", &t);
while (t > 0) {
scanf("%lld", &n);
for (i = 1; i <= n; i++) {
scanf("%lld", &A[i]);
}
P[0] = 0;
for (i = 1; i <= n; i++) {
P[i] = P[i - 1] + A[i];
}
total = P[n];
ans = 1;
MN = 0;
for (i = 1; i <= n; i++) {
M[i] = P[i] - MN;
MN = min(MN, P[i]);
if (M[i] >= total) ans = 0;
}
if (ans == 1) printf("YES\n");
else printf("NO\n");
t--;
}
return 0;
}
'Algorithm Study > c++' 카테고리의 다른 글
| [C++] queue 사용 & 예제 (0) | 2023.06.09 |
|---|---|
| [C++] stack 사용 & 예제 (0) | 2023.06.09 |
| [C++] Prefix sum & static_cast / codeforces-276-C (0) | 2023.06.09 |
| [C++] Longest Increasing Subsequence / codeforces-486-E (0) | 2023.06.07 |
| [C++] Tree / codeforces-219-D (0) | 2023.06.06 |