[백준 26152] 플래피 버드 스코어링 (C++)

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

 

문제

---

플래피 버드는 장애물을 피해 최대한 멀리까지 도달하는 게임이다.

하나의 장애물을 피할 때마다 1점씩 점수를 얻게 된다. 게임에는 총 N개의 장애물이 존재하고, i번째 장애물은 두 개의 장애물로 표현된다. 상단 장애물 끝 지점의 위치는 𝐴_𝑖로 나타내어지고, 하단 장애물 끝 지점의 위치는 𝐵_𝑖로 나타내어진다.

플래피 버드 고수 세정이는 장애물이 어떤 식으로 주어지든 플래피 버드를 조작해 피할 수 있다. (단, 플래피 버드의 크기가 장애물의 틈새보다 클 경우에는 세정이도 장애물을 피하지 못한다.) 즉, 플래피 버드의 크기 𝑤가 장애물의 틈새보다 클 경우에는 장애물을 피하지 못한다. 이때, 장애물을 피하지 못하면 게임이 바로 끝나게 된다.

 

여러 종류의 플래피 버드가 각 게임마다 주어질 때, 해당 플래피 버드를 가지고 몇 점까지 획득할 수 있는지 구하려고 한다.

세정이의 게임 스코어를 구해 출력해보자.

 

입력

---

첫 번째 줄에는 장애물의 개수 𝑁이 주어진다. (1 ≤ 𝑁 ≤ 250 000)

두 번째 줄에는 상단 장애물의 위치 𝐴_𝑖가 공백으로 구분되어 주어진다. (−10⁹ ≤ 𝐴_𝑖 ≤ 10⁹)

세 번째 줄에는 하단 장애물의 위치 𝐵_𝑖가 공백으로 구분되어 주어진다. (−10⁹ ≤ 𝐵_𝑖 ≤ 10⁹) (이때, 주어지는 입력은 𝐵𝑖 ≤ 𝐴𝑖임이 보장된다.)

네 번째 줄에는 플레이할 플래피 버드의 개수 𝑄가 주어진다. (1 ≤ 𝑄 ≤ 250,000)

다섯 번째 줄에는 각 플래피 버드의 크기 𝑤_𝑖가 주어진다. (1 ≤ 𝑤_𝑖 ≤ 10⁹)

 

출력

---

각 플래피 버드별로 세정이가 얻을 수 있는 최대 게임 스코어를 각 줄마다 하나씩 출력한다.

 

문제 풀이

---

정렬을 이용한 문제.

새들의 크기를 기준으로 내림차순 정렬을 하면 i번째 새는 그 이전의 새들보다 크기가 같거나 작으므로 이전과 같은 점수이거나 더 많은 점수를 획득할 수 있다. 이를 이용해 투포인터 방식과 같이 while문을 사용하여 right를 증가시켜 해당 새가 넘을 수 있는 최대 개수를 구한 후 점수를 개별의 배열 points에 저장해둔다.

출력은 입력받은 새의 순서대로 출력해야 하기 때문에 pair를 사용하여 인덱스까지 같이 저장하여 정렬한 후 인덱스를 가져와 points에 저장될 수 있도록 한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, Q, B;
	int right = 0;
	cin >> N;
	long long* heights = new long long[N];
	for (int i = 0; i < N; i++)
	{
		cin >> heights[i];
	}
	for (int i = 0; i < N; i++)
	{
		cin >> B;
		heights[i] -= B;
	}
	cin >> Q;
	pair<int, int>* birds = new pair<int, int>[Q];
	int* points = new int[Q];
	for (int i = 0; i < Q; i++)
	{
		cin >> birds[i].first;
		birds[i].second = i;
		points[i] = 0;
	}
	sort(birds, birds + Q, greater<>());
	for (int i = 0; i < Q; i++)
	{
		while (right < N && heights[right] >= birds[i].first)
		{
			right++;
		}
		int index = birds[i].second;
		points[index] = right;
	}
	for (int i = 0; i < Q; i++)
	{
		cout << points[i] << "\n";
	}
	return 0;
}