백준: Gold4 - 1484, 1504

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

1484: 다이어트

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

a*2 - b*2 = G일 때 a 구하기

    for(int i = 1; i*i < g; i++){
        if( g % i == 0 ) d.push_back(i);
    }
    for(int i = 0; i < d.size(); i++){
        if( (g/d[i] + d[i] )%  2 == 1 ) continue;
        int a = (g/d[i] + d[i]) / 2;
        // int b =  (g/d[i] - d[i]) / 2;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    if( v.size() ){
        for(int a : v){
            cout << a << '\n';
        }
    }
    else cout << -1 << '\n';

i를 1부터 증가시키면서 이중 포문으로 다 검사해 보면 시간초과 날 거다.
그래서 생각한 게, a*2 - b*2 = (a+b)(a-b) = G이므로, G의 약수들만 확인해 보면 되겠더라.
(a-b) * (a+b) = Di * Dn-i = G이므로, 약수들 중 루트 G보다 작은 것들만 저장한다(a-b).

a-b = d
a+b = g/d
2a = g/d + d

로 식을 세울 수 있다. 훨씬 빠르다.

주의할 점은, 몸무게가 0이 될 수 없다는 거다. 약수(a-b)들을 구할 때 for문 종료 조건을 i*i < g로 하면 된다.

ex) G = 9
(a,  b)
(9,  0)     <- 불가능
(25, 16)    <- 답

</br>

1504: 특정한 최단 경로

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

1부터 n까지, v1과 v2를 꼭 거쳐서 가는 최단 경로

방법 1.

void dijkstra(int start){
    for(int i = 1; i <= n; i++){
        dist[i] = INT_MAX;
    }
    priority_queue<P, vector<P>, greater<P>> pq;
    dist[start] = 0;
    pq.push(mp(0, start));
    while( pq.size() ){
        int v = pq.top().second;
        int w = pq.top().first;
        pq.pop();

        if( dist[v] < w ) continue;

        for(int i = 0; i < graph[v].size(); i++){
            int u = graph[v][i].second;
            if( dist[u] > w + graph[v][i].first ){
                dist[u] = w + graph[v][i].first;
                pq.push(mp(dist[u], u));
            }
        }
    }
}

// in main()
    dijkstra(v1);
    v11 = dist[1];
    v1n = dist[n];
    v1v2 = dist[v2];
    dijkstra(v2);
    v2n = dist[n];
    v21 = dist[1];

    if( v1v2 == INT_MAX ) cout << -1 << endl;
    else if( v11 == INT_MAX || v2n == INT_MAX )
        if( v1n != INT_MAX && v21 != INT_MAX )
            cout << v1n + v21 + v1v2 << endl;
        else cout << -1 << endl;
    else if( v1n == INT_MAX || v21 == INT_MAX )
        cout << v11 + v2n + v1v2 << endl;
    else cout << min(v11 + v2n, v1n + v21) + v1v2 << endl;

다익스트라는 내나 그 다익스트라
경로를 생각해 보면,

1 - v1 - v2 - n         // 1
(1 == v1) - v2 - n      // 2
1 - v1 - (v2 == n)      // 3
1 - v2 - v1 - n         // 4

이 가능한데, 다익스트라에서 어차피 같은 노드 끼리의 거리는 0이므로 2, 3은 굳이 따로 고려해 줄 필요는 없었다.
따라서 v1-1, v2-v1, v2-n의 합과 v1-n, v2-v1, v2-1의 합 중 작은 걸 출력하면 된다.
만약 연결 되지 않을 경우도 있으므로 잘 고려해 주자
</br>

방법 2.

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

이 문제는 n이 800까지라서 O(V^3)인 플로이드 워셜로도 잘 풀린다.
</br>

---

굿
</br>