[도전 15일차] 경비행기, 두 배열의 합 - KOI 고등부 풀이

※복습 : 

 

문제 1 : 백준 2585 경비행기

문제 링크

 

사용 알고리즘 : 이분탐색 (Parametric Search), BFS

 

풀이: 

기름 용량이 X일 때 시작점 부터 도착점까지  경로 중 경유지 수의 최소값을 B(X) 라 하자.

기름 용량이 크면 클수록, 한 경유지에서 갈 수 있는 경유지의 수가 많아지므로

Xi <= Xj 이면 B(Xi) >= B(Xj) 이다.

 

이분탐색은 정렬되어 있는 집합에서 사용할 수 있으므로 X가 1~(시작점-도착점 거리) 일 때

B(X) 집합에 대하여 이분탐색을 수행할 수 있다.

 

BFS를 수행하면서 거리를 중복 계산할 수 있기 때문에 모든 거리를 미리 구해 놓았다.

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end())
const int INF = 1e9;
using namespace std;
int n,k,dist[1010][1010],vis[1010];
pair<int,int> arr[1010];
queue<int> q;
void get_dist(){
    for(int i=0;i<n+1;i++)
        for(int j=1;j<=n+1;j++){
            int x=arr[i].first-arr[j].first,y=arr[i].second-arr[j].second;
            dist[i][j]=dist[j][i]=int(ceil(sqrt(x*x+y*y)/10.0));
        }
}
int bfs(int cnt){
    while(!q.empty())q.pop();
    memset(vis,0,sizeof(vis));
    q.push(0); vis[0]=0;
    if(dist[0][n+1]<=cnt)
        return 0;
    while(!q.empty()){
        int cur=q.front(); q.pop();
        for(int i=1;i<=n;i++)
            if(!vis[i] && dist[cur][i]<=cnt){
                vis[i]=vis[cur]+1;
                if(dist[i][n+1]<=cnt)
                    return vis[i];
                q.push(i);
            }
    }
    return INF;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>k;
    arr[0]={0,0}; arr[n+1]={10000,10000};
    for(int i=1;i<=n;i++)
        cin>>arr[i].first>>arr[i].second;
    get_dist();
    int lb=1,rb=dist[0][n+1];
    while(lb<rb){
        int mb=(lb+rb)/2;
        int calc=bfs(mb);
        if(calc<=k) rb=mb;
        else lb=mb+1;
    }
    cout<<lb;
}

 

※복습 : 

문제 2: 백준 2143 두 배열의 합 

문제 링크

 

사용 알고리즘 : 해싱 ( STL unordered_map 사용)

 

풀이: 

두 배열의 크기가 1000 이하로 작으므로, 구간합 배열을 통해 모든 연속합을 구할 수 있다.

sum[i] = a[1] + ... + a[i] 로 정의할 때  range_sum(i,j) = sum[j] - sum[i-1] 임을 이용하자.

 

=> 이중 반복문을 통해 모든 연속합을 구하여 각각 Vector에 넣는다.

 

여기까지는 모두 같고 3가지 풀이가 있다.

1. 해싱

한 벡터에서 unordered_map 에 각각의 원소의 개수를 저장한다.

다른 쪽 벡터의 원소들을 살펴본다. 편의상 이 값을 x라고 하면 unordered_map 에 저장되어 있는 T-x의 값을 더해준다.

 

2. 이분탐색

두 벡터를 정렬한다. 한 벡터의 원소들을 살펴보면서 편의상 이 값을 x라고 하면 T-x를 다른 쪽 벡터에서 이분탐색을 통해 찾는다

 

3. 투 포인터

두 벡터를 정렬한다. 한 포인터(p1) 는 1번 벡터의 처음, 다른 포인터(p2)는 2번 벡터의 마지막을 보면서  (v1[p1] + v2[p2] <T )이면 p1++, (v1[p1]+v2[p2] >T ) 이면 p2-- , 

(v1[p1]+v2[p2] == T) 이면 각각의 원소의 개수를 세서 곱해주어 정답에 더해준다. 

두 벡터는 정렬되어 있으므로 정답구간을 항상 살펴볼 수 있다.

 

아래 코드는 1번 방법을 사용했다.

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end())
const int INF = 1e9;
using namespace std;
unordered_map<int,int> mp;
int T,n,m,arr[1001],b[1001];
ll ans;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>T;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>arr[i],arr[i]+=arr[i-1];
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>b[i],b[i]+=b[i-1];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            mp[arr[j]-arr[i-1]]++;
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++){
            int target=T-(b[j]-b[i-1]);
            if(mp.count(target))
                ans+=mp[target];
        }
    cout<<ans;
}

 

 

궁금한 점이 있으시다면 질문 남겨주세요 :)