BOJ 17393, 다이나믹 롤러
ProblemSolving ·이 문제는 이분탐색 문제이다.
(어려운 문제가 아닌데 푸신 분들이 별로 안계셔서 포스팅해보았습니다!)
풀이
문제가 장황하게 설명되어있지만 사실 핵심은 간단합니다.
첫 번째 배열(input)이의 원소의 위치가 1이라고하면 원소의 위치가 1보다 큰 두 번째 배열(com) 중에서 첫번째 배열(1번째 원소)보다 값이 작거나 같은 원소의 수를 출력하면 된다!
(input[i]보다 작거나 같은 값의 수 com[i+1],com[i+2],com[i+3], … , com[n-1] 중에서)
값의 범위가 커서 long long 형을 사용했습니다. 두 번째 배열은 오름차순으로 입력을 받기 때문에 그것을 이용해서 이분탐색을 해주면 되겠습니다. input[i]보다 커지는 com배열의 위치를 찾고 i값을 빼주면 갯수를 구할 수 있겠습니다.
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<functional>
#include<stack>
using namespace std;
typedef long long ll;
ll input[500001];
ll com[500001];
int main()
{
ll n;
scanf("%lld", &n);
for (int i = 0; i < n; i++)
scanf("%lld", &input[i]);
for (int i = 0; i < n; i++)
scanf("%lld", &com[i]);
for (ll i = 0; i < n; i++)
{
ll left = i+1, right = n - 1;
while (left <= right)
{
ll mid = (left + right) / 2;
if (com[mid] > input[i])
right = mid - 1;
else
left = mid + 1;
}
printf("%lld ", right-i);
}
return 0;
}