2023.06.24 골랜디

[A] 텔레포트 3 - boj 12908번

 

우선 두 점 (xi, yi) 와 (xj, yj) 사이 점프로 이동해서 걸리는 시간은 | xi - xj | + | yi - yj | 입니다. 이 점을 활용해 임의의 두점 사이 걸리는 시간을 O(1)에 계산할수 있습니다. 텔레포트의 갯수가 3개로 고정되어 있기 때문에 텔레포트를 타는 모든 6C3 개의 조합에 대해 답을 계산 해주면 대충 6!=720개 정도의 조합이 나오고 각 조합에 대한 경로를 O(1)시간에 구할수 있기 때문에 충분히 빠르게 답을 구할수 있습니다.

 

6C3 개의 조합을 전부 돌아보는 과정은 C++의 next_permutation함수를 이용해 쉽게 구현할수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

#define PRECISION 0

#define fr first
#define sc second

using ll = long long;
using ld = long double;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll MOD = 1e9+7;

pair<pll, pll> tel[10];

int main(){
    ll xs, ys, xe, ye;
    cin >> xs >> ys >> xe >> ye;

    for(int i=1; i<=3; i++){
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        tel[i] = {{x1,y1}, {x2,y2}};
        tel[i+3] = {{x2,y2}, {x1,y1}};
    }

    ll ans = abs(ye-ys) + abs(xe-xs);
    // 최초 답 = 텔레포트 0개 써서 도착
    
    vector<int>tmp = {1,2,3,4,5,6};
    //텔레포트를 타는 순서
    
    do{
        ll tmp1 = 10;
        //여기서부턴 텔레포트를 적어도 하나는 탄거니까 10
        
        for(int i=0; i<3; i++){
            if(i!=0) tmp1 += (abs(tel[tmp[i]].fr.sc - tel[tmp[i-1]].sc.sc) + abs(tel[tmp[i]].fr.fr - tel[tmp[i-1]].sc.fr) + 10);
            //i가 0이 아니라면, 즉, 두개 이상의 텔레포트를 탔다면 두 텔레포트 사이 걸리는 거리를 더함
            ll tmpans = tmp1 + abs(xs-tel[tmp[0]].fr.fr) + abs(ys-tel[tmp[0]].fr.sc) + abs(xe-tel[tmp[i]].sc.fr) + abs(ye-tel[tmp[i]].sc.sc);
            //tmpans 는 i번째 텔레포트까지만 탔을때 비용, 따라서 tmp1 에 0번째 텔레포트까지 점프하는 비용 과 i번째 텔레포트에서 끝점으로 점프하는 비용이 추가됨
            ans = min(ans, tmpans);
            //답은 이중 최소
        }
    }while(next_permutation(tmp.begin(), tmp.end()));
    //모든 순서를 확인하고 섞어주기 위해 next_permutation 사용
    
    cout << ans;
}

[B] Succession/왕위 계승 - boj 5021번

 

https://youtu.be/3SjU1n_2bnw

 

이렇게 이상한 족보가 따로 없습니다.

 

map을 사용해 각 이름을 정점 번호에 매핑 시켜준후 위상 정렬을 해주면 족보의 몇대손(?) 인지에 따라 순서대로 볼수 있게 됩니다. 

 

그 후 이렇게 형성된 DAG에서 dp를 통해 문제에 주어진 조건대로 각 부모에서 혈통 (dist)값을 절반씩 가져오면 됩니다.

 

그 후 m개의 후보중 혈통값이 가장 높은 후보가 답이됩니다.

 

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

#define PRECISION 0

#define fr first
#define sc second

using ll = long long;
using ld = long double;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll MOD = 1e9+7;

map<string, pair<string, string>> par;
map<string, int> mp;
map<int, string> mpi;

vector<int>edges[105];
int vis[105];
ll dist[105];

int inDegree[105];

int n, m;

void dfs(int cur){
    vis[cur] = 1;
    for(int &nxt:edges[cur]){
        if(vis[nxt]) continue;
        dist[nxt] = dist[cur] + 1;
        dfs(nxt);
    }
}

int main(){
    cin >> n >> m;
    fill(dist, dist+100, 0);
    string founder;
    cin >> founder;
    mp[founder] = 1;
    mpi[1] = founder;
    dist[1] = (1LL)<<60;
    int cur = 1;
    for(int i=0; i<n; i++){
        string child, parent1, parent2;
        cin >> child >> parent1 >> parent2;
        if(!mp[child]){
            mp[child] = ++cur;
            mpi[cur] = child;
        }
        if(!mp[parent1]){
            mp[parent1] = ++cur;
            mpi[cur] = parent1;
        }
        if(!mp[parent2]){
            mp[parent2] = ++cur;
            mpi[cur] = parent2;
        }
        edges[mp[parent1]].push_back(mp[child]);
        edges[mp[parent2]].push_back(mp[child]);
        inDegree[mp[child]] += 2;
        par[child] = {parent1, parent2};
    }

    queue<pii>q;

    vector<pair<int, string>> v;

    for(int i=1; i<=cur; i++){
        if(inDegree[i]==0) q.push({i,1});
    }
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        v.push_back({cur.sc, mpi[cur.fr]});
        for(auto nxt:edges[cur.fr]){
            inDegree[nxt]--;
            if(inDegree[nxt]==0) q.push({nxt, cur.sc+1});
        }
    }

    sort(v.begin(), v.end());

    for(int i=0; i<v.size(); i++){
        string cur = v[i].sc;
        if(par.find(cur)!=par.end()){
            dist[mp[cur]] = dist[mp[par[cur].fr]]/2 + dist[mp[par[cur].sc]]/2;
        }
    }

    vector<pair<ll, string>> ans;
    
    for(int i=0; i<m; i++){
        string tmp;
        cin >> tmp;
        ans.push_back({dist[mp[tmp]], tmp});
    }

    sort(ans.begin(), ans.end(), greater<pair<ll, string>>());

    cout << ans[0].sc;
}

 

[C] 기하가 너무 좋아 - boj 28067번

 

O((nm)^3) 에 세 점의 후보로 가능한 모든 점을 확인할수 있습니다. 이렇게 뽑은 세점이 이루는 삼각형의 세 변들의 길이를 묶어서 set에다 집어넣어줍니다.

 

여기서 주의할점은 이 세 점의 조합중 삼각형이 되지 않는것은 걸러줘야 한다는겁니다. 저는 CCW를 사용했지만 a < b + c (삼각형 세변 조건) 을 사용해도 괜찮습니다.

 

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

#define PRECISION 0

#define fr first
#define sc second

using ll = long long;
using ld = long double;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll MOD = (1LL)<<32;

ll n, m;

int sgn(ll x){ return (x > 0) - (x < 0); }

ll dist(pll p1, pll p2){
    return ((p1.fr-p2.fr)*(p1.fr-p2.fr) + (p1.sc-p2.sc)*(p1.sc-p2.sc));
}

int ccw(pair<ll,ll>p1, pair<ll,ll>p2, pair<ll,ll>p3){
    ll temp1 = p1.fr*p2.sc + p2.fr*p3.sc + p3.fr*p1.sc;
    ll temp2 = p1.sc*p2.fr + p2.sc*p3.fr + p3.sc*p1.fr;
    ll res = temp1 - temp2;
    return sgn(res);
}


set<tuple<ll, ll, ll>> s;

int main(){
    cin >> n >> m;

    for(ll i1=0; i1<=n; i1++){
        for(ll j1=0; j1<=m; j1++){
            for(ll i2=0; i2<=n; i2++){
                for(ll j2=0; j2<=m; j2++){
                    for(ll i3=0; i3<=n; i3++){
                        for(ll j3=0; j3<=m; j3++){
                            pll p1 = {i1, j1};
                            pll p2 = {i2, j2};
                            pll p3 = {i3, j3};

                            if(p1==p2 || p1==p3 || p2==p3){
                                continue;
                            }
                            if(p1.fr == p2.fr && p2.fr == p3.fr) continue;
                            if(p1.sc == p2.sc && p2.sc == p3.sc) continue;

                            if(ccw(p1, p2, p3)==0) continue;

                            ll d1 = dist(p1, p2);
                            ll d2 = dist(p2, p3);
                            ll d3 = dist(p3, p1);

                            vector<ll>tmp = {d1, d2, d3};
                            sort(tmp.begin(), tmp.end());
                            
                            s.insert({tmp[0], tmp[1], tmp[2]});
                        }
                    }
                }
            }
        }
    }

    cout << s.size() << endl;

    /*for(auto i:s){
        cout << get<0>(i) << ' ' << get<1>(i) << ' ' << get<2>(i) << endl;
    }*/
}