BOJ 8983 C++

백준 8983 C++ 풀이

문제 접근

동물들의 위치와 사대의 위치를 이용하여 이분탐색을 하면된다.

사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는

xi-aj

+ bj

코드로 보면

int val = abs(pos[mid] - animal_pos[apos].first) + animal_pos[apos].second;

pair를 이용해 x좌표와 y좌표를 받아 사대와 동물간의 거리를 구했다.

우리가 찾아야할 값은 잡을 수 있는 동물의 수 이므로 ‘val’ 즉 사대와 동물가느이 거리가 주어졌을 때 그 거리에 있는 동물을 잡을 수 있는 사대가 있는지 찾으면 되므로 사대 배열에서 맞출 수 있는 사대가 있는지 찾으면 되겠다.

코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;


bool ebun(const vector<int>& pos, int len, const vector<pair<int, int>> &animal_pos,int apos)
{
	int lo = 0;
	int hi = pos.size() - 1;
	bool cnt = 0;
	while (lo <= hi)
	{
		
		int mid = (lo + hi) / 2;
		int val = abs(pos[mid] - animal_pos[apos].first) + animal_pos[apos].second; //사대와 동물간의 거리.
		if (val <= len) //만약 거리가 사정거리 보다 작거나 같으므로 맞출 수 있다.
		{
			cnt = true;
			break;
		}
        //사대의 사정거리가 생겨먹은걸 잘 봐라.
		if (pos[mid] < animal_pos[apos].first) //현재의 사대가 동물의 x좌표보다 작으므로 오른쪽으로 이동한다
			lo = mid + 1;
		else//현재의 사대가 동물의 y좌표보다 크므로 왼쪽으로 이동한다.
			hi = mid - 1;
	}
	return cnt;
}



int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int m, n, l; cin >> m >> n >> l;
	vector<int> pos(m);
	for (int i = 0; i < m; i++)
		cin >> pos[i];
	vector<pair<int, int>> animal_pos(n);
	for (int i = 0; i < n; i++)
		cin >> animal_pos[i].first >> animal_pos[i].second;
	sort(pos.begin(), pos.end());
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (ebun(pos, l, animal_pos,i)) //i번째 동물
			ans++;
	}
	cout << ans;
	return 0;
}

시도 해본 풀이

사대와 동물의 거리를 모두 찾아 arr배열에 저장하고 정렬한뒤 lower_bound와 upperbound를 이용하여 잡을 수 있는 동물의 최초 등장하는 arr에서의 주소와 마지막에 등장하는 arr에서의 주소까지 전부 mal 배열에 true로 초기화 하여 true의 수 만큼 카운팅 하려고 했다. 하지만 정해를 보고 난뒤 생각해보니 비효율적이고 어려운 코드같다. 완벽히 구현을 하지는 않았지만 이 방법도 되지 않을까.

#include <bits/stdc++.h> 
#define ll long long
using namespace std;

ll arr[100000];
bool mal[100000];

void dist(const vector<pair<ll, ll>>& x, int pos)
{
    int size = x.size();
    for (int i = 0; i < size; i++)
    {
        arr[i] = abs(pos - x[i].first) + x[i].second;
    }
    sort(arr, arr + size);
}

int ebun_hi(const vector<pair<ll, ll>>& x, ll len)
{
    int size = x.size();
    int lo = 0;
    int hi = size - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (arr[mid] > len)
        {
            hi = mid - 1;
        }
        else
        {
            lo = mid + 1;
        }
    }
    return hi;
}

int ebun_low(const vector<pair<ll, ll>>& x, ll len)
{
    int size = x.size();
    int lo = 0;
    int hi = size - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (arr[mid] >= len)
        {
            hi = mid - 1;
        }
        else
        {
            lo = mid + 1;
        }
    }
    return hi;
}


int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int m, n;
    ll l;
    cin >> m >> n >> l;
    vector<ll> pos(m);
    for (int i = 0; i < m; i++)
        cin >> pos[i];
    vector<pair<ll, ll>> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].first >> v[i].second;
    for (int i = 0; i < m; i++)
    {
        dist(v, pos[i]);
        int lo = ebun_low(v, l);
        int hi = ebun_hi(v, l);
        for (int i = lo; i < hi + 1; i++)
        {
            mal[i] = true;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
        if (mal[i])
            ans++;
    cout << ans;
    return 0;
}