[백준 17393] 다이나믹 롤러 (C++)

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

문제

---

페인팅 전문 회사 부키치 암즈는 거대한 페인팅용 롤러 "다이나믹 롤러"를 출시하였다. 이 신제품은 평범한 페인팅 롤러와 마찬가지로 굴려서 칠할 수 있지만, 손잡이를 세로로 휘둘러 잉크를 한번에 흩뿌릴 수도 있도록 설계되었다. 이러한 새로운 사용방법은 거대한 몸집과 맞물려 매우 역동적으로 보였기 때문에, 이 롤러의 이름은 다이나믹 롤러가 되었다. 평소 페인팅에 관심이 많던 멩미는 다이나믹 롤러의 매력에 흠뻑 빠져, 단숨에 다이나믹 롤러를 구매했다. 지금 당장 롤러를 시험해 보고 싶었던 멩미는 통로 일부분을 칠해보기로 했다.

통로는 1 × N 길이의 일자 형태를 가지고 있고, 통로의 바닥은 1 × 1 타일로 가득 차있다. 각 타일은 잉크지수 A_i 와 점도지수 B_i 를 가지고 있다. 타일이 제각각 다른 특성을 가지고 있기 때문에, 멩미는 세심하게 롤러를 휘둘러야만 한다. 멩미가 i 번째 타일 위에 서 있을 때, 멩미는 다이나믹 롤러로 현재 위치보다 오른쪽에 있으면서 점도지수가 서 있는 칸의 잉크지수 A_i 이하인 칸을 칠할 수 있다.

통로는 기본적인 관리가 되고 있기 때문에, 각 칸의 잉크지수 A_i 는 점도지수 B_i 이상이다. 그러나 깊숙한 통로는 관리에 어려움이 있기 때문에, 점도지수 B_i 는 항상 오름차순이다. 이런 상황 속에서 멩미가 통로의 각 타일에서 서 있을 때 다이나믹 롤러로 칠할 수 있는 최대의 칸 수를 구해보자.

 

입력

---

첫 번째 줄에 통로의 길이인 자연수 N이 입력으로 주어진다. (1 ≤ N ≤ 5 × 10⁵)

두 번째 줄에 N개의 정수 A₁, A₂, ..., A_N이 공백으로 구분되어 주어진다. A_i 는 i 번째 칸의 잉크지수를 의미한다. (1 ≤ Aᵢ ≤ 10¹⁸)

세 번째 줄에 N개의 정수 B₁, B₂, ..., B_N이 공백으로 구분되어 주어진다. Bi 는 i 번째 칸의 점도지수를 의미한다. (1 ≤ Bᵢ ≤ 10¹⁸, A_i ≥ B_i)

B₁, B₂, ..., B_N은 오름차순이다. 즉, 1 ≤ i ≤ j ≤ N을 만족하는 모든 정수 순서쌍 (i, j)에 대해 B_i ≤ B_j 가 성립한다.

 

출력

---

첫 번째 줄에 N개의 정수 x₁, x₂, ..., x_N을 공백으로 구분하여 출력한다. x_i는 i 번째 칸에 서서 다이나믹 롤러를 사용할 때 최대로 칠할 수 있는 칸의 개수이다.

 

문제 풀이

---

이분 탐색 문제.

 

잉크를 칠할 수 있는 칸은 현재 서 있는 칸의 잉크 지수보다 큰 점도 지수를 가진 칸이면서 현재 서 있는 칸보다 오른쪽이어야 한다. 점도 지수 B는 오름차순이므로 이분 탐색을 이용해 해결할 수 있다.

찾는 값보다 처음으로 큰 값을 구하는 upper_bound()를 사용한 후 1을 빼주면 칠할 수 있는 최대 위치를 구할 수 있게 된다.

 

A와 B가 최대 10¹⁸이므로 long long으로 입력 받는 것을 잊지 말자.

 

아래는 코드.

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

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

	int N;
	cin >> N;
	long long* arr = new long long[N];
	long long* viscocity = new long long[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (int i = 0; i < N; i++)
	{
		cin >> viscocity[i];
	}
	for (int i = 0; i < N; i++)
	{
		int index = upper_bound(viscocity, viscocity + N, arr[i]) - viscocity;
		cout << max(index - i - 1, 0) << " ";
	}
	return 0;
}