[백준] 17393: 다이나믹 롤러

문제 링크

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

접근 방식 / 풀이

N개의 잉크 지수 A와, 점도 지수 B가 입력으로 들어온다.
자신의 오른쪽에 있는 $B_j$ 값들 중에서 자신의 현재 값 $A_i$ 이하인 개수를 세는 문제이다. $1 \le N \le 5 \times 10^5$이고, 브루트 포스로 진행한다면 시간복잡도가 $O(N^2)$ 이기에, 이분탐색으로 진행해야 한다.

이를 해결하기 위해 upper_bound()를 사용했다.
C++ <algorithm> 헤더에 있는 upper_bound() 함수는 정렬된 벡터의 처음과 끝 iterator, 그리고 찾을 값을 인자로 넣으면, 이분 탐색을 진행하여, 해당 값을 초과하는 값 중 제일 작은 값을 가리키는 iterator를 반환한다.
문제 조건 중 $B$는 오름차순으로 주어졌다고 했기 때문에 정렬 과정을 거칠 필요 없이 upper_bound()를 사용해도 무방하다.

우리는 $B$에서 $A_i$ 이하의 값 중 최댓값의 인덱스를 찾아야 하기에, upper_bound(b.begin(), b.end(), a[i])의 리턴값 인덱스의 이전 값이 우리가 원하는 인덱스 값이다. 위 값에서 $i$를 빼주면 답이 도출된다.

이 때, 문제 조건에서 $A_i \ge B_i$라고 주어졌기 때문에, upper_bound()로 얻은 $B_{j+1}$의 인덱스 값은 최소 $i + 1$이며, $B_j$와 $i$의 인덱스 차이는 최소 $0$이기에 음수인 경우는 나오지 않으므로 신경쓰지 않아도 된다.

---

답안 코드 링크 (Github)

Github Solution Link

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void	fastio(void);

int main(void)
{
	vector<long long>	a, b;
	long long	n, tmp, size;
	
	fastio();
	cin >> n;
	for (int i = 0; i < n; i++)	{
		cin >> tmp;
		a.push_back(tmp);
	}
	for (int i = 0; i < n; i++)	{
		cin >> tmp;
		b.push_back(tmp);
	}
	for (int i = 0; i < n; i++) {
		size = upper_bound(b.begin(), b.end(), a[i]) - b.begin() - i - 1;
		cout << size;
		if (i != n - 1)
			cout << " ";
	}
	cout << "\n";
	return (0);
}

void	fastio(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}