Life Engineering
[BOJ 7578] 공장 (C++) 본문
https://www.acmicpc.net/problem/7578
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll *tree;
vector<pair<int,int> > v;
ll query(int left, int right, int node, int queryLeft, int queryRight){
if (right<queryLeft || queryRight<left){
return 0;
}
else if (queryLeft<=left && right<=queryRight){
return tree[node];
}
else{
int mid=(left+right)/2;
return query(left, mid, node*2, queryLeft, queryRight)+query(mid+1, right, node*2+1, queryLeft, queryRight);
}
}
void update(int left, int right, int node, int machine_num){
if (left<=machine_num && machine_num<=right){
tree[node]+=1;
if (left!=right){
int mid=(left+right)/2;
update(left, mid, node*2, machine_num);
update(mid+1, right, node*2+1, machine_num);
}
}
}
bool compare(pair<int,int> a, pair<int,int> b){
return a.second<b.second;
}
int binarySearch(int target, int start, int end){
while (start<=end){
int mid=(start+end)/2;
if (v[mid].second<target){
start=mid+1;
}
else if (v[mid].second>target){
end=mid-1;
}
else{
return v[mid].first;
}
}
return 0;
}
int main(){
int N, x, S=1;
ll ans=0;
cin>>N;
int machines[N+1];
for (int i=1; i<=N; i++){
cin>>x;
v.push_back(make_pair(i,x)); //first: 인덱스 second: 머신넘버
}
sort(v.begin(), v.end(), compare);
for (int i=1; i<=N; i++){
cin>>x;
machines[i]=binarySearch(x,0,N-1);
}
while (S<N){
S*=2;
}
tree=new ll[S*2];
memset(tree, 0, sizeof(ll)*(S*2));
for (int i=1; i<=N; i++){
ans+=query(1,S,1,machines[i]+1,N); //count bigger number than me so far
update(1,S,1,machines[i]);
}
delete[] tree;
cout<<ans<<"\n";
return 0;
}
말해뭐해.. 역시나 플래티넘답게 어려움.
첨에 접근방식을 잘못해서 인덱스드 트리를 쓰긴 썼는데 mintree, maxtree 따로 만들고 조건따져서 sum..했는데 답이 다 이상하게 나왔다.. 결국 힌트 참고..
[구현 방법]
1,2,3,4,5
2,4,1,3,5
이렇게 있으면 자기 기준으로 왼쪽에 있는 수들이 자기보다 크면 케이블이 발생한다는 아이디어.
그래서 인덱스드 트리를 이용해 자기(i)보다 큰 애들 [i+1, N] 의 수를 세주면 된다. 그리고 자기가 연결될 때 인덱스드 트리를 +1 씩(자기가 속한 구간에 한해 모두) 증가시켜주면 된다.
아이디어를 떠올리고-이걸 인덱스드 트리와 연결하는 과정이 중요했다.
그리고 map으로 인덱스를 지정하니 TLE 발생. pair로 인덱스,머신번호 묶어줘서 정렬한 뒤 이분탐색으로 해결했다.(백준 큐앤에이 참고했다)
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 문자열 압축 (C++) (0) | 2021.08.30 |
---|---|
[BOJ 17427] 다리 만들기 (C++) (0) | 2021.08.26 |
[BOJ 1238] 파티 (C++) (0) | 2021.08.19 |
[BOJ 17070] 파이프 옮기기 (C++) (0) | 2021.08.19 |
[BOJ 3830] 교수님은 기다리지 않는다 (C++) (0) | 2021.08.18 |