백준 2661 - 좋은 수열
문제 설명
KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, ..., xM은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a1, b1), (a2, b2), ..., (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다.
사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는 |xi-aj| + bj로 계산한다.
예를 들어, 아래의 그림과 같은 사냥터를 생각해 보자. (사대는 작은 사각형으로, 동물의 위치는 작은 원으로 표시되어 있다.) 사정거리 L이 4라고 하면, 점선으로 표시된 영역은 왼쪽에서 세 번째 사대에서 사냥이 가능한 영역이다.
사대의 위치와 동물들의 위치가 주어졌을 때, 잡을 수 있는 동물의 수를 출력하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/8983
제한 사항
풀이
문제를 요약하면 동물과 사대의 위치 정보가 주어졌을 때 각 사대에서 봤을 때 사거리 L안에 있는 동물의 수를 출력하면 된다.
주의할 점은 사냥할 수 있는 동물의 수를 출력해야 하기 때문에 문제처럼 사대를 기준으로 동물을 체크한다면 중복으로 체크할 가능성이 있다.
따라서 동물을 기준으로 사대와의 위치를 계산하면 중복을 자연스럽게 제거할 수 있다.
가장 간단한 방법으로 N마리의 동물이 M개의 사대와의 거리를 계산해서 L이하일 때 정답의 개수를 올리는 방법이 있다.
이 방법은 명백히 정답을 구할 수 있지만 시간 초과가 발생한다.
그렇다면 시간을 줄이기 위해 다른 방법을 사용해 보자.
사대는 y좌표가 0으로 고정되어 있다.
즉, x좌표만 존재하기 때문에 일차원 배열로 표현이 가능하다.
그렇다면 동물과의 거리를 구하기 위해서는 동물의 y좌표를 0으로 만들면 모두 일직선으로 표현할 수 있다.
일직선 상에 표현된 점들은 거리를 구하는게 매우 쉽고 빠른 시간 안에 구하는 방법이 존재한다.
바로 이진 탐색을 하는 것이다.
정리하자면 동물의 y좌표를 0으로 만든다. 이때, 이동한 y좌표만큼 L에서 빼주어 거리를 갱신한다.
int dist = L - y;
if (dist < 0) continue;그럼 동물의 x좌표에서 dist만큼 왼쪽으로 그리고 오른쪽으로 이동시킨 지점을 사대에서 찾아내면 된다.
auto leftIdx = lower_bound(shootPoints.begin(), shootPoints.end(), x - dist) - shootPoints.begin();
auto rightIdx = upper_bound(shootPoints.begin(), shootPoints.end(), x + dist) - shootPoints.begin();
if (leftIdx < rightIdx)
{
ans++;
}
이때 주의할 점은 left는 lower_bound이고 right는 upper_bound이다.
이는 이진 탐색의 결과가 주어진 수보다 큰 수를 찾는 규칙때문이다.
만약 둘 다 lower_bound를 사용하여 계산한다면 if문에서 leftIdx와 righIdx가 같을 때도 처리해 줘야 한다.
정확히 사대의 위치와 겹치는 상황도 카운팅해야 하기 때문이다.
하지만 이렇게 되면 논리에 오류가 생길 수 있다.
예를 들어, 만약 사대의 위치가 9라고 해보자.
L이 4이고 동물이 (8, 4)에 있다고 해보자.
lower_bound를 사용하면 leftIdx, rightIdx 모두 위치가 9인 사대를 가리키게 된다.
이렇게 되면 이 동물은 사냥이 가능하다고 판단되어 카운팅 하게 되는데 사실 이는 오류이다.
사거리가 4이기 때문에 9인 사대에서는 이 동물을 사냥할 수 없다.
따라서 오른쪽은 upper_bound로 포함되지 않은 범위를 체크해야 한다.
전체 코드
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
using namespace std;
int M, N, L;
vector<int> shootPoints;
int main()
{
INPUT_OPTIMIZE;
cin >> M >> N >> L;
shootPoints.resize(M);
for (int i = 0; i < M; i++)
{
cin >> shootPoints[i];
}
sort(shootPoints.begin(), shootPoints.end());
int ans = 0;
for (int i = 0; i < N; i++)
{
int x, y;
cin >> x >> y;
int dist = L - y;
if (dist < 0) continue;
auto leftIdx = lower_bound(shootPoints.begin(), shootPoints.end(), x - dist) - shootPoints.begin();
auto rightIdx = upper_bound(shootPoints.begin(), shootPoints.end(), x + dist) - shootPoints.begin();
if (leftIdx < rightIdx)
{
ans++;
}
}
cout << ans;
return 0;
}