급하게임개발

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

이 문제는 일단 누적합을 이용해서 구간들의 합을 구해야 하는데 구간합간의 단순 비교를 하면 시간 초과가 뜨기 때문에 이문제의 경우 일단 한 배열의  구간 합들을 따로 저장 해놓고  이를 정렬한 후 이분탐색으로 그값의 하위 인덱스와 상위인덱스의 차를 더해주면 된다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> valOfA;
vector<int> valOfB;
vector<int> cmpB;
int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	iostream::sync_with_stdio(false);
	int t;
	int n, m;
	cin >> t;
	cin >> n;
	valOfA.resize(n + 1,0);
	int tmp;
	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		valOfA[i] = tmp + valOfA[i - 1];
	}
	cin >> m;
	valOfB.resize(m + 1, 0);
	for (int i = 1; i <= m; i++) {
		cin >> tmp;
		valOfB[i] = tmp+ valOfB[i - 1];
	}

	for (int i = 0; i <= m; i++) {
		for (int j = i+1 ; j <= m; j++) {
			cmpB.push_back(valOfB[j] - valOfB[i]);
		}
	}
	sort(cmpB.begin(), cmpB.end());
	int start = 1;
	int subAarr = 0;
	long long ans = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			subAarr =valOfA[j] - valOfA[i];
			subAarr = -(subAarr)+t;
			int lowIdx = lower_bound(cmpB.begin(), cmpB.end(),subAarr) - cmpB.begin();
			int upIdx = upper_bound(cmpB.begin(), cmpB.end(), subAarr) - cmpB.begin();
			ans += upIdx - lowIdx;
		}
	}
	cout << ans;

}

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

이 문제는 재시도를 엄청 했다 첫번째 풀이로는 평범하게 사용하는 누적합을 사용해서 풀어보았다. 실버3이라서 확실히 이런 기초적인 코딩을 쓰지는 않았을 거 같지만 일단 해보았다. 당연히 시간초과가 발생했다. 그럼 무슨 알고리즘을 써야할까 알아보다 슬라이딩 윈도우 알고리즘이라는 기억 어딘가에 쳐박아놓은 알고리즘이 생각 났다. 이에 iostream의 cin과 cout을 stdio와 sync까지 끊고 코드를 작성하였음에도 시간초과가 발생했다. 이에 3번째에서는 iostream을 stdio.h 로 바꾸고 실행하니까 정상 적으로 실행 되었다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;
int N;
int M;
int arr[100001] = { 0, };
int i, j;
int main() {

	int temp1, temp2;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
		arr[i] = arr[i] + arr[i - 1];
	}
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &temp1, &temp2);
		printf("%d\n", arr[temp2] - arr[temp1 - 1]);
	}
}

이런 식으로 배열에 누적값을 저장해 줌으로서 범위를 구할 때 2 5를 입력했을 때를 예시로들면 5까지 입력한 값에서 1까지 누적된값을 빼면 2에서5의 누적값이 나온다 기존에 누적시키는 것보다 O(1)의 시간밖에 걸리지 않아 시간초과 가 발생하지 않는다.