백준: Gold4 - 1240, 1253

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

1240: 노드사이의 거리

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

트리에서 노드 사이 거리 구하기

void func(int u, int v, int d){
    if( u == v ){
        ans = min(ans, d);
        return;
    }
    visited[u] = 1;
    for(int i = 0; i < tree[u].size(); i++){
        P p = tree[u][i];
        if( visited[p.second] == 0 ){
            func(p.second, v, d+p.first);
            visited[p.second] = 0;
        }
    }
}

// in main()
    while( m-- ){
        int u, v;
        cin >> u >> v;
        ans = INT_MAX;
        memset(visited, 0, (n+1)*sizeof(int));
        func(u, v, 0);
        cout << ans << endl;
    }

그래프 안에 트리가 있으므로 그냥 그래프에서 두 정점 사이 거리 구하기로 봤다
memset(visited, 0, (n+1)*sizeof(int)); 실수로 memset에서 n+1을 안 하고 n으로 해서 한 번 틀림… 인덱스 주의하자
</br>

1253: 좋다

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

다른 두 수의 합으로 이뤄지는지 확인하기 입력이 1 1 2의 경우 1+1 = 2이므로 가능하다.

방법 1.

    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++){
        if( v[i].second < 0 ) continue;
        int d = v[i].first;
        int l = 0, h = v.size()-1;

        while( l < h ){
            int mid = v[l].first + v[h].first;
            if( mid == d ){
                if( l == i ) l++;
                else if( h == i ) h++;
                else{
                    cnt += v[i].second;
                    break;
                }
            }
            else if( mid < d ) l++;
            else h--;
        }
    }

이분 탐색으로 풀었다 그런데 이걸 투 포인터라 부르는 거 같기도 하고??
아무튼 양 끝에서 시작해서 걔를 찾을 때까지 양쪽을 조절해 주면 된다. 계산 횟수를 줄이려고 처음에 맵으로 입력 받아 같은 수를 여러 번 탐색하는 경우를 뺐다.

방법 2.

    if( zero >= 3 ) cnt += zero;
    bool makezero = false;
    for(pair<int, int> p : m){
        if( p.second > 1 ){
            if( zero ){
                cnt += p.second;
                m[p.first] = -1;
            }
            else if( m.count(2*p.first) ){
                cnt += m[2*p.first];
                m[2*p.first] = -1;
            }
        }
        if( zero <= 2 && m.count(-p.first) ) makezero = true;
    }
    if( makezero ) cnt += zero;

계산 횟수를 좀 더 줄여 보려고, 0을 따로 세서 처리해 주는 작업도 먼저 하고 위 코드를 돌려 봤는데, 별로 줄어 들진 않았다…!!
</br>

---

160문제를 풀었다 굿
</br>