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

최초 업로드: 2025-11-15 16:38:44

최근 수정 시간: 2025-11-15 16:38:44

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 플래피 버드 스코어링

[문제 링크](https://www.acmicpc.net/problem/26152)

## 문제 설명

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

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

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

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

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

## 입력

첫 번째 줄에는 장애물의 개수 $N$이 주어진다. $(1 \le N \le 250\ 000)$

두 번째 줄에는 상단 장애물의 위치 $A_i$가 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$

세 번째 줄에는 하단 장애물의 위치 $B_i$가 공백으로 구분되어 주어진다. $(-10^9 \le B_i \le 10^9)$ (이때, 주어지는 입력은 $B_i \le A_i$임이 보장된다.)

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

다섯 번째 줄에는 각 플래피 버드의 크기 $w_i$가 주어진다. $(1 \le w_i \le 10^9)$

## 출력

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

## 풀이
q를 내림차순으로 정렬하여 큰 새부터 먼저 지나가게 하고, 막힌 지점부터 그것보다 살짝 작은 새를 지나가게 하고... 아이디어를 활용한 오프라인 쿼리로 풀었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int a[250'000];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<n;i++) cin >> a[i];
 for(int i=0;i<n;i++) {
 int b; cin >> b;
 a[i] -= b;
 }

int q; cin >> q;
 vector<pair<int, int>> v(q);
 for(int i=0;i<q;i++) {
 cin >> v[i].first;
 v[i].second=i;
 }
 sort(v.begin(), v.end(), greater<pair<int, int>>());

int idx=0;
 vector<int> res(q);
 for(auto &[val, i]:v) {
 while(idx<n && val<=a[idx]) idx++;
 res[i]=idx;
 }
 for(int i=0;i<q;i++) cout << res[i] << '\n';
}
```