백준: Class 3 ⑨ - 16928, 17219, 17626, 18870

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

16928: 뱀과 사다리 게임

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

    for(int i = 0; i < n + m; i++){
        int x, y;
        cin >> x >> y;
        graph[x] = y;
    }
                        // +, -
    priority_queue< pair<int, int>, vector<pair<int, int>>, greater<> > pq;
    pq.push(make_pair(0, -1));
    visited[1] = 1;
    int ans;
    while( pq.size() ){
        int d = pq.top().first;
        int x = -pq.top().second;
        pq.pop();
        if( x == 100 ){
            ans = d;
            break;
        }
        for(int i = 1; i <= 6; i++){
            if( x+i > 100 ) continue;
            if( graph[x+i] )
                if( visited[graph[x+i]] == 0 ){
                    pq.push(make_pair(d+1, -graph[x+i]));
                    visited[graph[x+i]] = 1;
                }
            else if( visited[x+i] == 0 ){
                pq.push(make_pair(d+1, -(x+i)));
                visited[x+i] = 1;
            }
        }
    }
    cout << ans << endl;

딱 보니까 뱀 타는 게 더 유리할 수도 있는 테스트 케이스를 만들어 놨을 것 같다
아무튼 이번에도 우선순위 큐를 사용했다. 현재 주사위를 던진 수가 가장 작고, 현재 위치는 큰 순이다.
나머지는 그냥 그대로 사다리나 뱀 타고 가게 구현하기
</br>

17219: 비밀번호 찾기

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

    map<string, string> mp;
    while( n-- ){
        string s, pw;
        cin >> s >> pw;
        mp[s] = pw;
    }
    while( m-- ){
        string s;
        cin >> s;
        cout << mp[s] << '\n';
    }

굉장히 쉽네
</br>

17626: Four Squares

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

    for(int i = 1; i <= 50000; i++){
        dp[i] = 4;
    }
    for(int i = 1; i*i < 50000; i++){
        dp[i*i] = 1;
        if( i*i == n ){
            cout << 1 << endl;
            return 0;
        }
    }
    for(int i = 2; i <= n; i++){
        for(int j = 1; j*j < i; j++){
            dp[i] = min(dp[i], dp[i-j*j] + 1);
        }
    }
    cout << dp[n] << endl;

나는… dp가 좋아
4개 합이 된다는 건 증명 되었으니 전부 일단 4로 초기화 하고, 제곱수들은 1로 초기화 한다. 혹시 제곱수 중 n을 발견하면 바로 종료한다.
dp[i] = min(dp[i], dp[i-제곱수들] + 1)이다.

ex) 26
dp[26] = min(dp[26-1] + 1, dp[26-4] + 1, ..., dp[26-25]+1);

</br>

18870: 좌표 압축

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

    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        v.push_back(make_pair(a, i));
    }
    sort(v.begin(), v.end());
    int ind = 1, prev = v[0].first;
    v[0].first = v[0].second;
    v[0].second = 0;
    for(int i = 1; i < n; i++){
        if( v[i].first != prev ){
            prev = v[i].first;
            v[i].first = v[i].second;
            v[i].second = ind++;
        }
        else{
            v[i].first = v[i].second;
            v[i].second = ind-1;
        }
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n; i++){
        cout << v[i].second << ' ';
    }
    cout << '\n';

좌표 압축이란 건 처음 보네 신기하다
처음 입력 받을 때 (값, 인덱스)로 저장하고, 정렬한다.
따라서 값이 작은 순으로 정렬되어 있다.
다시 저장할 땐 (인덱스, 압축된 좌표)로 저장한다.
그리고 정렬하면 원래 입력 받은 순서대로 압축된 좌표를 출력할 수 있다.
페어 순서 바꾼 거는 cmp함수 만들기 귀찮아서ㅋㅋ
</br>

---

클래스 3을 다 풀었다!! 3++이 되었다
270문제 풀었고 정답률은 57.203%
포스트는 아마 23일 쯤에 올라갈 예정이지만 지금은 16일 밤 방학 끝까지 2주 남았구나
방학 안에 랭킹 50등 안에도 들고 싶고 플레 5도 찍어보고 싶은데 가능할까
</br>