백준: 20044, 20040, 20046

</br> 작년에 알고리즘 아무것도 모르는 채로 ICPC에 나갔던 적이 있다
그 때 총 한 문제 풀었나ㅜㅜ 나는 아무 것도 안 하고 틀린 추측만 하고 팀에 폐만 끼쳤다

지금은 그 때보단 당연히 낫긴 한데 문제 풀이 시작한 지 기껏해야 한 달 좀 넘은 물렙이라 모르겠다… 좀 더 일찍 많이 열심히 할 걸
</br>

20044: Project Teams

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

#include <bits/stdc++.h>

using namespace std;

int nums[10001];

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

    int n;
    cin >> n;

    for(int i = 0; i < 2*n; i++){
        cin >> nums[i];
    }

    sort(nums, nums+2*n);

    int ans = INT_MAX;
    for(int i = 0; i < n; i++){
        ans = min(ans, nums[i] + nums[2*n-i-1]);
    }

    cout << ans << endl;

}

I번이다 제일 쉬움
그냥 정렬해서 양 끝 더한 거의 최솟값을 구하면 된다
</br>

20040: 사이클 게임

https://cyj893.github.io/algorithm/Algorithm17_5/
전에 이미 푼 문제
그냥 Union find 쓰면 끝
그냥 모르면 뻘짓하거나 못 푸는 문제
많이 풀어보는 게 참 중요하다

</br>

20046: Road Reconstruction

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

#include <bits/stdc++.h>

using namespace std;

int mmap[1001][1001];
int visited[1001][1001];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

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

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> mmap[i][j];
            visited[i][j] = -1;
        }
    }

    if( mmap[0][0] == -1 || mmap[n-1][m-1] == -1 ){
        cout << -1 << '\n';
        return 0;
    }

    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    pq.push(make_tuple(mmap[0][0], 0, 0));
    visited[0][0] = mmap[0][0];

    while( pq.size() ){
        int d = get<0>(pq.top());
        int x = get<1>(pq.top());
        int y = get<2>(pq.top());
        pq.pop();

        if( x == n-1 && y == m-1 ) break;

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( nx < 0 || n <= nx || ny < 0 || m <= ny ) continue;
            if( visited[nx][ny] != -1 || mmap[nx][ny] == -1 ) continue;
            pq.push(make_tuple(d+mmap[nx][ny], nx, ny));
            visited[nx][ny] = d + mmap[nx][ny];
        }
    }

    cout << visited[n-1][m-1] << '\n';

}

bfs다 근데 이제 우선순위 큐를 곁들인 그럼 다익스트라인가?
그냥… 간단히… 갈 수 있는 곳이면 비용을 그만큼 더하고 우선순위 큐에 넣고… 우선순위 큐는 비용 작은 순으로 하고
너무 쉬운 문젠데 모여서 연습할 때 자꾸 틀려서(괄호를 안 붙임) 민망했음
</br>

---

9월을 열심히
</br>