[풀이] N<=100000 이므로 N^2개의 모든수의 짝을 구해보기엔 시간이 오래걸리므로 이분탐색을 이용하였습니다. 배열 A를 정렬시킨 뒤, A[i] (i:0~N-1)를 고정시키고 A[i]~A[N-1] 의 숫자 중 조건을 가장 잘 만족시키는 숫자 A[j]를 찾으면 됩니다. A[j]-A[i] >= M 이 조건이므로 A[i]~A[N-1]의 숫자 A[j] 중 A[j] >= A[i]+M 을 만족하는 j를 lower_bound를 이용해 찾을 수 있습니다.
아래 코드와 같이 lower_bound(a+i,a+N,a[i]+M) 는 a[i]+M 이상인 최솟값의 iterator를 반환하므로 (반환된 iterator:it)-A 의 값이 곧 index j의 값이 됩니다. A[j]-A[i]는 정답의 후보가 될 수 있으므로 ans 값을 업데이트 해주면 됩니다.
#include <algorithm>
#include <cstdio>
using namespace std;
using ll = long long;
int N;
ll M,a[100001];
int main(){
scanf("%d%lld",&N,&M);
for(int i=0;i<N;i++) scanf("%lld",&a[i]);
sort(a,a+N);
int ans = 2e9;
for(int i=0;i<N;i++){
int idx = lower_bound(a+i,a+N,a[i]+M)-a;
if(idx<N) ans = min(int(a[idx]-a[i]),ans);
}
printf("%d",ans);
}
[풀이] 구간을 몇개로 나누어야 하는지, 어디를 기준으로 나누어야 하는지를 찾으려고 하면 N 제한이 5000이므로 무리가 있습니다.
이런 방법들 대신에 최종적으로 구해야하는 답인 "구간의 점수의 최댓값의 최솟값"에서 "구간의 점수의 최댓값" 을 어떤 수 m으로 고정해놓고 구간을 나눠보는 방식을 사용할 수 있습니다.
어떤 구간의 점수도 m 이상이 되도록 구간을 나누었을 때, 총 구간의 개수가 M 이하라면 이 m의 값은 정답이 될수도 있는 값이지만 최솟값은 아닙니다. 이 m의 값을 조금씩 줄여가면서 답이 될 수 있는지 확인해보는 이분탐색을 이용하면 시간내에 최적의 m 값을 찾을 수 있습니다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,a[5001];
bool check(int m){
int cnt=0;
int minv=a[0],maxv=a[0];
for(int i=0;i<=N;i++){
minv=min(minv,a[i]);
maxv=max(maxv,a[i]);
int diff = maxv-minv;
if(diff<=m) continue;
cnt++;
minv=maxv=a[i];
}
return cnt<=M;
}
int sol(){
int lo=-1,hi=10000;
while(lo+1<hi){
int mid=(lo+hi)/2;
if(check(mid)) hi=mid;
else lo=mid;
}
return hi;
}
int main(){
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++) scanf("%d",&a[i]);
a[N]=1e5;
printf("%d",sol());
}
[풀이] 규칙성을 찾아서 수학적 수식으로 푸는것이 정해인 것 같은데 무식하게 이분탐색으로 풀었습니다.
A<= x <=B 인 x에 대해 x가 2^k * p (k>=1) 꼴로 나타내지는 것들에 대해서는 2^k 만큼 더해주면 됩니다.
결국 B를 넘지 않는 모든 2^k에 대해 A<= 2^k * p <=B 를 만족하도록 하는 p의 범위를 구해주면 됩니다.
이를 이분탐색으로 구할 수 있습니다. A<= 2^k * left <= 2^k* right <= B A보다 크거나 같게 만드는 left, B보다 작거나 같게 만드는 right를 이분탐색으로 각각 구하면 right-left+1 만큼이 A<= 2^k * p <=B 를 만족하는 p의 개수가 됩니다. 결국 정답 ans에 2^k * (right-left+1)를 더해주면 됩니다.
주의할 것이 k의 최댓값부터 반대로 검사를 해주면서 acnt (정답에 포함된 A<= x <= B 인 x의 개수) 를 누적해주어야 합니다. 2^k 에서 답에 누적된 x들은 2^(k-1) 에 반드시 포함되므로 이것을 빼줘야 하기 때문입니다. 그래서 right-left+1 대신 right-left+1-acnt를 사용하였습니다.
[풀이] 어떤 코어에서 일의 처리가 완료될때마다 그 코어에 새로운 작업을 할당해주고, 나머지 코어의 일의 남은 시간을 업데이트 하는 방식을 생각할 수 있는데 이런 방식으로는 코어의 개수 N이 10000, 처리해야할 일의 개수가 50000개 이므로 O(N*M)이 되어 시간내에 해결할 수가 없습니다.
이런 유형의 문제에는 이분탐색(파라메트릭 서치)를 이용해야 합니다.
최저시간 low=-1, 최고시간 high=200000로 두고 어떤 시간 mid가 지났을 때, 처리한 총 일의 개수 cnt를 기준으로 low 혹은 high를 mid로 업데이트해줍니다.
(코어의 수가 2개, 각각의 처리시간은 10000, 총 일의 개수가 50000일때가 시간이 가장 오래 걸리는 케이스입니다. 이때 모든 일을 처리하는데 (10000*50000)/2 시간이 걸리는데 high을 200000 정도로만 잡아도 통과를 합니다. TC가 부족한 것 같습니다.)
처리한 총 일의 개수는 (mid(시간)/cores[i])+1 들의 합으로 구할 수 있습니다. 예를 들어 일 한개를 처리하는데 2시간이 걸리는 코어의 일처리 과정을 시간별로 보면 아래와 같이 (현재 시간을 코어의 처리시간으로 나눴을 때의 몫)+1 으로 표현됩니다.
0시간 : 1개 1시간 : 1개 2시간 : 2개 3시간 : 2게 4시간 : 3개 5시간 : 3게 6시간 : 4개 7시간 : 4개 ....
이 때 목표 처리 물건 개수 n보다 적게 만드는 시간 중에 최고 시간이 lo로 수렴하도록 해야합니다. 이렇게 하면 lo+1 시간에 어떤 코어 i에 물건을 할당하면 최종적으로 n개를 처리할 수 있기 때문입니다. 0번 코어부터 N-1번 코어부터 확인하면서 lo+1 시간에 물건을 할당할 수 있는지를 검사해서 할당할 수 있으면 lo시간까지 처리한 물건의 개수에 1개씩 더해줍니다. (lo+1)%cores[i]==0 을 만족하면 lo+1시간에 물건 할당이 가능하다는 것을 위의 일처리 과정 예시를 보면 확인할 수 있습니다.
lo가 -1로 나온 경우는 처리해야할 일의 개수가 코어 개수보다 적은 것이므로 n번째 일을 처리하는 n번 코어를 리턴해주기만 하면 됩니다.
이런 유형의 문제를 이분탐색으로 처리할 생각을 하기가 쉽지는 않지만 꽤 자주 보이는 전형적인 유형이므로 익혀두면 도움이 될 것 같습니다.
#include <vector>
#include <cstdio>
using namespace std;
int solution(int n, vector<int> cores) {
int lo=-1,hi=2e5,mid=0;
while(lo+1<hi){
mid = (lo+hi)/2;
int cnt=cores.size();
if(mid>0) for(int i=0;i<cores.size();i++) cnt+=mid/cores[i];
if(cnt<n) lo=mid;
else hi=mid;
}
if(lo==-1) return n;
int cnt=cores.size();
for(int i=0;i<cores.size();i++) cnt+=lo/cores[i];
for(int i=0;i<cores.size();i++){
if((lo+1)%cores[i]==0) cnt++;
if(cnt==n) return i+1;
}
return 0;
}
위와 같이 sum(j+1,k)와 sum(i,j)가 같아야 하기 때문에 1~j까지의 합 sum[j]에 sum(j+1,k) 인 (sum[j] - sum[i-1])를 더한 값이 부분합 배열에 존재하면 sum(j+1,k) == sum(i,j) 가 만족되어 각 아들이 가진 과자 수 sum[j] - sum[i-1]가 정답의 후보가 될 수 있습니다.
이 후보들을 이용해 최댓값을 갱신해 주면 최종 답을 구할 수 있습니다.
#include <vector>
#include <algorithm>
using namespace std;
int N,answer;
int solution(vector<int> cookie) {
N=cookie.size();
cookie.insert(cookie.begin(),0);
vector<int> sum(N+1);
for(int i=1;i<=N;i++) sum[i]=sum[i-1]+cookie[i];
for(int i=1;i<=N-1;i++){
for(int j=i;j<=N-1;j++){
int t = 2*sum[j]-sum[i-1];
int idx = lower_bound(sum.begin(),sum.end(),t)-sum.begin();
if(idx<=N && sum[idx]==t) answer=max(sum[j]-sum[i-1],answer);
}
}
return answer;
}
3) 매 탐색에서 나오는 mid를 이용해 "바위들간의 가장 가까운 거리는 기껏해야 mid이다" 이렇게 정의를 하면 0 -> rocks[0] -> rocks[1]... 순으로 방문할 때 rocks[j]-rocks[i]의 거리가 mid보다 멀면 rocks[j]는 제거된 바위로 간주하면 됩니다.
i) 남아있는 바위의 개수가 rocks.size()-n (남아있어야할 바위의 개수) 보다 크다면, mid를 조금 더 큰 수를 사용해볼 수 있기 때문에 mid=lo 로 업데이트 하고 다음 시행으로 넘어갑니다. (잘 생각해보면 mid가 커질수록 남아있는 바위의 수는 적어지고, mid가 작아질수록 남아있는 바위의 수는 커지기 때문입니다.)
ii) 남아있는 바위의 개수가 rocks.size()-n보다 더 적다면 바위를 더 남겨야합니다. 그러려면 mid를 더 줄여서 더 간격이 좁은 바위도 포함될 수 있도록 해야합니다. hi=mid로 업데이트 해주고 다음 시행으로 넘어갑니다.
위의 시행을 반복하다보면 lo와 hi가 1 차이가 나는 상황까지 수렴하게 됩니다. 이때의 lo 값이 최적의 값이므로 이 값을 return하면 됩니다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
sort(rocks.begin(),rocks.end());
int lo=0, hi=distance+1;
while(lo+1<hi){
int mid=(lo+hi)/2;
int cnt=0;
int cur=0;
for(int i=0;i<rocks.size();i++){
if(rocks[i]-cur>=mid) {
cnt++;
cur=rocks[i];
}
}
if(cnt>=rocks.size()-n) lo=mid;
else hi=mid;
}
return lo;
}
[풀이] 당연히 그냥 구현 문제일줄 알았는데 info의 범위가 50000 query의 범위가 100000이나 되기 때문에 쿼리마다 모든 info를 확인하는 O(query*info)의 시간복잡도로는 효율성 테스트 통과가 불가능합니다.
지원자의 4가지 항목을 4자리 수로 변환해주는 Hashing과 어떤 점수를 넘는 지원자를 찾기 위한 binary search를 사용해주면 문제를 해결할 수 있습니다.
1) 아래와 같이 4가지 항목으로 숫자로 변환해주는 map 테이블을 만듭니다. cpp, java, python => 1,2,3 backend, frontend => 1,2 junior, senior => 1,2 chicken, pizza => 1,2
2) 지원자의 정보 string을 분리하여 hash값을 만든 뒤 map> 타입의 map에 형태로 저장합니다. ex) mp["1111"].push_back(150) 그 뒤 map을 순회하면서 vector들을 정렬해줍니다. (binary search를 사용하기 위함입니다.)
3) query를 순회하면서 string을 쪼개서 만들 수 있는 모든 hash를 만들어줍니다. 저는 vector 4개를 선언하여 "-" 가 아닌 경우에는 그에 맞는 string의 변환값을 넣어주었고, "-"인 경우에는 1,2 (언어의 경우 3까지) 모두 되므로 모두 vector에 넣어준 뒤 4중 for문을 돌려서 만들 수 있는 모든 hash를 만들어주었습니다. query가 -,-,-,- 이어도 최대 3x2x2x2=24개 이기때문에 많은 시간이 들지 않습니다.
각 2)에서 저장한 hash key에 맞는 점수들이 저장되어있는 vector를 map에서 가져와 binary search를 통해 조건을 만족하는 가장 적은 점수의 지원자의 iterator를 가져옵니다. mp[key].end()-it를 통해 조건을 만족하는 모든 지원자를 구할 수 있습니다. 이 값을 cnt 변수에 카운트해주면 최종 cnt 값이 현재 query의 정답입니다.