백준: Class 5 - 2098, 2887

</br> 클래스 5 계속
</br>

2098: 외판원 순회

https://www.acmicpc.net/problem/2098

int dp[17][65536];
int graph[17][17];
int n, endset;

int func(int ii, int kk){
    if( kk == endset ){
        if( graph[ii][0] != 0 ) return graph[ii][0];
        return MAX;
    }

    if( dp[ii][kk] != MAX ) return dp[ii][kk];

    for(int k = 0; k < n; k++){
        if( !(kk & (1 << k)) && graph[ii][k] != 0 ){
            int s = kk | (1 << k);
            dp[ii][kk] = min(dp[ii][kk], func(k, s) + graph[ii][k]);
        }
    }
    return dp[ii][kk];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    endset = (1<<n)-1;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> graph[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int k = 0; k < (1<<n); k++){
            dp[i][k] = MAX;
        }
    }

    cout << func(0, 1) << endl;

}

이제 슬슬 비트로 dp하기(이전 상태 다 저장하기)가 익숙해지는 거 같다
근데 바텀 업으로 하니까 잘 모르겠어서 탑 다운으로 했다.
외판원 순회는 한 곳에서 출발한 경우만 봐도 된다. 만약 1에서 시작한 최적 경로가 1-2-3-4-5-1이라면, 2에서 시작한 최적 경로는 2-3-4-5-1-2일 것이 당연하기 때문이다.

</br>

2887: 행성 터널

https://www.acmicpc.net/problem/2887

struct UnionFind{
    vector<int> parent, ran;
    UnionFind(int n) : parent(n), ran(n, 1) {
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }
    int f(int u){
        if( u == parent[u] ) return u;
        return parent[u] = f(parent[u]);
    }
    bool merg(int u, int v){
        u = f(u); v = f(v);
        if( u == v ) return false;
        if( ran[u] > ran[v] ) swap(u, v);
        parent[u] = v;
        ran[v] += ran[u];
        ran[u] = 0;
        return true;
    }
};

// in main()
    for(int i = 0; i < n; i++){
        int a, b, c;
        cin >> a >> b >> c;
        x[i] = make_pair(a, i);
        y[i] = make_pair(b, i);
        z[i] = make_pair(c, i);
    }
    sort(x, x+n);
    sort(y, y+n);
    sort(z, z+n);
    priority_queue<T, vector<T>, greater<>> pq;
    for(int i = 1; i < n; i++){
        pq.push(make_tuple(x[i].first - x[i-1].first, x[i].second, x[i-1].second));
        pq.push(make_tuple(y[i].first - y[i-1].first, y[i].second, y[i-1].second));
        pq.push(make_tuple(z[i].first - z[i-1].first, z[i].second, z[i-1].second));
    }

    UnionFind uf = UnionFind(n);
    int ans = 0;
    while( pq.size() ){
        int w = get<0>(pq.top());
        int a = get<1>(pq.top());
        int b = get<2>(pq.top());
        pq.pop();

        if( uf.merg(a, b) ) ans += w;
    }

    cout << ans << endl;

오랜만에 또 크루스칼 문제다
주의할 점은 행성 수가 10만이라서 메모리와 시간 문제로 엣지를 다 비교할 수는 없다. 따라서 각각 정렬 후에 가까운 애들끼리만 넣어준다.

</br>

---

오늘은 8월 28일
방학 안에 학교 랭킹 50등 안쪽하고 플래티넘 5 가기 했는데 성공했다
그래도 물렙이니까 열심히 복습도 하고 앞으로도 꾸준히 풀자
</br>