2024-04-01

오늘은 만우절!

-수들의 합 2(2003, 백준)

 쉬운 2포인터 문제라고 생각했다. 시작점에 low, high를 잡아주고, m을 기준으로 투포인터를 돌리면 풀리는 간단한 문제이다. 풀고보니 O(N^2)도 돌아간다고 한다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
vector <int> vec;
int ans;

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		vec.push_back(x);
	}vec.push_back(0);
	int low = 0, high = 0;
	int res = vec[0];
	while (low < n && high < n) {
		if (res == m) res += vec[++high], ans++;
		else if (res < m) res += vec[++high];
		else res -= vec[low++];
	}
	printf("%d", ans);
}

-화살표 그리기(15970, 백준)

 2018초등부 2번문제다. 색갈이 모두 다른 점들이 주어졌을 때 같은색중 가장 최소의 거리를 갖는 점과의 거리를 모두 더하는 문제이다. 각 색별로 따로 배열에 저장후 정렬해준다. 그 뒤, 순서대로 돌아가앞뒤 점중 가장 작은 점과의 거리를 ans에 더하면 된다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector<int> vec[5010];

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		vec[y].push_back(x);
	}
	for (i = 1; i <= n; i++) {
		if (vec[i].size() == 0) continue;
		else sort(vec[i].begin(), vec[i].end());
	}
	int ans = 0;
	for (i = 1; i <= n; i++) {
		if (vec[i].size() == 0) continue;
		for (j = 0; j < vec[i].size(); j++) {
			int res = 2e9;
			if (j > 0 && res > vec[i][j] - vec[i][j - 1]) res = vec[i][j] - vec[i][j - 1];
			if (j < vec[i].size() - 1 && vec[i][j + 1] - vec[i][j] < res) res = vec[i][j + 1] - vec[i][j];
			ans += res;
		}
	}
	printf("%d", ans);
	return 0;
}

-수 고르기(2230, 백준)

 쉬운 2포인터 문제다. 마찬가지로 시작점에 low와 high를 잡은뒤, m을 기준으로 차의 투포인터를 돌려주면 쉽게 풀린다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
vector <int> vec;

int main() 
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		vec.push_back(x);
	}
	int ans = 2e9;
	sort(vec.begin(), vec.end());
	int low = 0, high = 0;
	while (low < n && high < n) {
		int res = vec[high] - vec[low];
		if (res < m) {
			high++;
		}
		else {
			ans = min(ans, res);
			low++;
		}
	}
	printf("%d", ans);
	return 0;
}

-XCorr(15976, 백준)

 아이디어가 생각보다 쉽게 떠올랐다. 문제에서 주어지지않은 배열의 idx값은 0임으로, 서로의 채워진 배열끼리 만나는 경우를 구하면 된다. 즉 문제에서 주어진 a, b범위내에서 만나는 배열의 값끼리만 곱해서 더해주면 된다. 이때 a, b범위내에 있는 배열은 연속함으로, 누적합을 이용해 한번에 구할 수 있다. 배열의 범위값을 찾는데는 2분탐색 lower bound를 이용했다.

y배열의 누적합 구하기 -> x좌표 탐색해가면서 현재 idx + a와 idx + b에 가까운 수를 y의 idx배열에서 찾기(lower_bound) -> 범위 내의 누적합 * 현재 x배열의 값을 ans에 더해주기 -> ans 출력

lower_bound에서 +m을 해야되는데 +n을 해놓고 1시간동안 못찾아서 시간 증발 ㅠ.ㅠ

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

long long n, m;
long long vx_idx[300010], vx_val[300010];
long long vy_idx[300010], vy_val[300010], sumy[300010];
long long a, b;

int main()
{
	long long i, j;
	scanf("%lld", &n);
	for (i = 1; i <= n; i++) scanf("%lld %lld", &vx_idx[i], &vx_val[i]);
	scanf("%lld", &m);
	for (i = 1; i <= m; i++) scanf("%lld %lld", &vy_idx[i], &vy_val[i]);
	for (i = 1; i <= m; i++) sumy[i] = sumy[i - 1] + vy_val[i];
	scanf("%lld %lld", &a, &b);
	long long ans = 0;
	for (i = 1; i <= n; i++) {
		long long idx = vx_idx[i], val = vx_val[i];
		long long low = lower_bound(vy_idx + 1, vy_idx + m + 1, idx + a) - (vy_idx);
		long long high = lower_bound(vy_idx + 1, vy_idx + m + 1, idx + b) - (vy_idx);
		if (high > m) high--;
		if (vy_idx[high] > idx + b) high--;
		ans += val * (sumy[high] - sumy[low - 1]);
	}
	printf("%lld", ans);
	return 0;
}