1. prefix sum

prefix sum은 누적합을 이야기 함
주로 테크닉을 이야기 함

prefix sum : 미리 계산값을 저장

조금더 DP에 가까운 문제로 보인다.

문제

11659 구간 합 구하기 4

구간 합 구하기 문제는 문제 제한이 크기 때문에 시간 제한 안에 통과할 수 있는 문제는 아니다.
O(NM)의 시간이 걸린다.

그래서 prefix sum을 사용해 보자

위와 같이 pre table을 이미 작성하면 4,6까지의 합을 구할 수 있게 된다.

이와 같이 미리 합을 계산하고 출력을 하면 N번의 반복문만을 돌면 되기 때문에 O(N)만에 문제를 끝낼 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	cin >> n >> m;
	vector<ll> a(n+1);
	vector<ll> pre(n+1);
	pre[0] = 0;
	for (i = 1; i <= n; ++i) {
		int temp;
		cin >> temp;
		a.push_back(temp);
		pre[i] = pre[i - 1] + temp;
	}
	while (m--) {
		int s, e;
		cin >> s >> e;
		int ans = 0;
		cout << pre[e]-pre[s-1] << '\n';
	}
}

하지만 이렇게 하다가 중간에 값이 바뀌면 아무 이득이 없어진다.

그래서 '세그먼트 트리'를 이용하면 연산과정이 O(log(logN))의 시간이 걸리게 된다.

11660 구간 합 구하기 5

이 문제도 구간 합 구하기 4와 유사하게 문제를 풀게 된다.

구하고자 하는 부분의 위쪽, 왼쪽을 빼고고 공통되는 부분을 더해주면 된다.

그렇다면 이러한 방식을 위해서 pre[i][j]를 어떻게 구현할 수 있을까?

정답은 아래의 식을 이용하고
𝑎𝑛𝑠 = 𝑝𝑟𝑒[𝑐][𝑑] − 𝑝𝑟𝑒[𝑎 − 1][d] − 𝑝𝑟𝑒[c][𝑏 − 1] + 𝑝𝑟𝑒[𝑎 − 1][𝑏 − 1]

정답을 구하기 위한 pre 배열은 아래의 식을 이용해서 구할 수 있다.
𝑝𝑟𝑒[𝑖][𝑗] = 𝑝𝑟𝑒[𝑖][𝑗 − 1] + 𝑝𝑟𝑒[𝑖 − 1][𝑗] − 𝑝𝑟𝑒[𝑖 − 1][𝑗 − 1] + 𝐴[𝑖][𝑗];

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
int a[1025][1025];
int pre[1025][1025];

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= n; ++j) {
			cin >> a[i][j];
			pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
		}
	}
	while (m--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		cout << pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1] << '\n';
	}
}

2. two pointer

투 포인터는 배열내에서 각자 다른 원소를 가리키고 있는 2개의 포인트를 조작해가며 문제를 해결하는 방법

문제

2003 수들의 합 2

이 문제를 그냥 prefix sum으로 풀기에는 O(n^3)의 시간이 걸리기 때문에 불가능하다.

가장 간단한 풀이 방법은 two pointer을 이용해 원하는 값보다 작다면 b를 더해주고 크다면 1을 더해준다.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
vector<ll> a;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (i = 0; i < n; ++i) {
		ll temp;
		cin >> temp;
		a.push_back(temp);
	}

	int s = 0, e = 0;
	ll sum = 0;
	ll ans = 0;
	while (1) {
		if (sum >= m) sum -= a[s++];
		else if (e == n) break;
		else sum += a[e++];
		if (sum == m) ans += 1;

	}
	cout << ans << '\n';
}

1484 다이어트

다이어트라는 문제이다. 그냥 배열에 제곱수 다 더하고 투 포인터로 풀어보자

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
vector<ll> a;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll d = 0;
	cin >> d;

	for (ll i = 1; i < 200001; ++i) {
		a.push_back(i * i);
	}
	vector<ll> ans;
	ll s = 0, e = 0;
	ll diff = 0;
	while (1) {
		if (e >= a.size()) break;
		diff = a[e] - a[s];
		if (diff < d) e++;
		if(diff>d) s++;
		if (diff == d) {
			ans.push_back(sqrt(a[e]));
			e++;
		}
	}

	if (!ans.size()) {
		cout << "-1" << '\n';

	}
	else {
		for (ll i : ans) {
			cout << i << '\n';
		}
	}
	return 0;
}

1253 좋다

이 문제는 두개의 함정이 존재한다.
1. 숫자에는 음/양수가 존재한다.
2. 자신을 제외한 어떤 수도 가능하다.

따라서 투 포인터와 정렬을 이용해서 풀 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll n = 0;
	cin >> n;

	vector<ll> a(n);
	for (i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	ll ans = 0;
	for (int i = 0; i< n; ++i) {
		int s = 0, e = n - 1;
		ll target = a[i];
		while (s < e) {
			ll sum = a[s] + a[e];
			if (sum < target) {
				s+=1;
			}
			else if (sum > target) {
				e-=1;
			}
			else if(sum==target){
				if (s != i and e != i) {
					//cout << target << ' ' << a[s] << ' ' << a[e] << '\n';
					ans += 1;
					break;
				}
				else if (s == i) {
					s += 1;
				}
				else if(e==i){
					e -= 1;
				}
			}

		}
		
	}
	cout << ans << '\n';
}