백준: Gold4 - 1153, 1197(Kruskal)

</br> 계속 계속
</br>

1153: 네 개의 소수

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

소수 4개 합으로 표현하기

    if( n % 2 ){
        for(int i = 0; i <= n-6; i++){
            if( primes[i] && primes[n-5-i] ){
                cout << "2 3 " << i << ' ' << n-5-i << endl;
                return 0;
            }
        }
    }
    else{
        for(int i = 0; i <= n-6; i++){
            if( primes[i] && primes[n-4-i] ){
                cout << "2 2 " << i << ' ' << n-4-i << endl;
                return 0;
            }
        }
    }

골드바흐의 추측을 사용한다고 한다 사실 찾아 봄…ㅋㅋ
4중 포문하니까 당연히 시간 초과 난다

2보다 큰 모든 짝수는 2개의 소수의 합으로 표현 가능하다.

따라서 n이 짝수면 2, 2를 빼고, 홀수면 2, 3을 빼서 새로운 짝수를 만들어 내고, 걔의 2개의 소수 합을 찾는다.
</br>

1197: 최소 스패닝 트리

https://www.acmcpc.net/problem/1197

최소 스패닝 트리의 가중치 구하기

    priority_queue<T, vector<T>, greater<T>> pq;
    for(int i = 0; i < e; i++){
        int a, b, c;
        cin >> a >> b >> c;
        pq.push(mt(c, a, b));
        parent[a] = a;
        parent[b] = b;
    }
    int ans = 0;
    while( pq.size() ){
        T t = pq.top();
        pq.pop();
        int ta = get<1>(t);
        int tb = get<2>(t);
        if( parent[ta] == parent[tb] ) continue;
        int p = min(parent[ta], parent[tb]);
        int pp = max(parent[ta], parent[tb]);
        for(int i = 1; i <= v; i++){
            if( parent[i] == pp ) parent[i] = p;
        }
        ans += get<0>(t);
    }
    cout << ans << endl;

크루스칼 알고리즘으로 풀어 보았다
일단 그래프에서 가중치가 적은 간선들 순으로 정렬한다.

ex)
i: 1 2 3 4 5
p: 1 2 3 4 5

(2, 4) 연결

i: 1 2 3 4 5
p: 1 2 3 2 5

(4, 5) 연결

i: 1 2 3 4 5
p: 1 2 3 2 2

(1, 2) 연결

i: 1 2 3 4 5
p: 1 1 3 2 2

i: 1 2 3 4 5
p: 1 1 3 1 1
2가 부모였던 애들도 부모를 1로 업데이트 해줌

대충 이런 식으로 부모를 업데이트 해주면, 같은 부모를 가지고 있는 간선끼리는 사이클이 생성 되므로 패스할 수 있다.
</br>

---

쭉 쭉
</br>