백준: Class 4 - 13549, 13172, 12865

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

13549: 숨바꼭질 3

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

    priority_queue< pair<int, int>, vector<pair<int, int>>, greater<> > pq;
    pq.push(make_pair(0, n));
    for(int i = 0; i < 100001; i++){
        visited[i] = INT_MAX;
    }
    visited[n] = 0;
    int ans;
    while( pq.size() ){
        int x = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if( x == k ){
            ans = d;
            break;
        }
        if( x+1 <= k && visited[x+1] > d ){
            pq.push(make_pair(d+1, x+1));
            visited[x+1] = d+1;
        }
        if( x-1 >= 0 && visited[x-1] > d ){
            pq.push(make_pair(d+1, x-1));
            visited[x-1] = d+1;
        }
        if( x != 0 && 2*x <= 100001 && visited[2*x] > d ){
            pq.push(make_pair(d, 2*x));
            visited[2*x] = d+1;
        }
    }
    cout << ans << endl;

저번에 푼 1697: 숨바꼭질(https://cyj893.github.io/algorithm/Algorithm15/)과 비슷한 문제다
달라진 건 순간이동할 때 아예 시간이 안 든다.
따라서, visited[2*x]보다 현재 d가 작을 경우 큐에 넣고 바꿔 주면 된다.
</br>

13172: Σ

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

int gcd(int a, int b){
    if( b > a ) return gcd(b, a);
    if( a%b == 0 ) return b;
    return gcd(b, a%b);
}

long long mypow(long long k, int d){
    if( d == 1 ) return k;
    if( d % 2 == 0 ){
        long long k2 = mypow(k, d/2);
        return k2*k2 % M;
    }
    else return k*mypow(k, d-1) % M;
}

// in main()
    int ans = 0;
    for(int i = 0; i < m; i++){
        int p, c;
        cin >> p >> c;
        int gcdpc = gcd(p, c);
        p /= gcdpc;
        c /= gcdpc;
        long long p1 = mypow(p, M-2);
        ans += c*p1 % M;
        ans %= M;
    }
    cout << ans << endl;

문제가 짱 긴데 읽으니 재밌다
정리하면 b^(X-2) ≡ b^(-1) (mod X) 이므로, 분수를 입력 받고 그 기약 분수를 a/b라 하면 (a × b^(-1)) mod 1000000007을 구해서 다 더하면 된다.
즉 1000000005 제곱을 해야 하므로 제곱 함수를 잘 만들어야 한다 이건데, b^(2*i) = b^i * b^i임을 사용해서 재귀 함수를 짤 수 있다.

        long long p1;
        if( mp.count(p) ) p1 = mp[p];
        else{
            p1 = mypow(p, M-2);
            mp[p] = p1;
        }

혹시 반복 계산을 줄여줄 수 있을까 싶어서 맵에 b^(-1)을 구한 걸 저장해 보는 코드를 넣어서 다시 제출해 봤는데, 메모리만 더 들고 시간은 똑같더라
</br>

12865: 평범한 배낭

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

int w[101];
int v[101];
int dp[101][100001];

// in main()
    for(int i = 0; i < n; i++){
        cin >> w[i] >> v[i];
        dp[i][w[i]] = v[i];
    }
    for(int i = w[0]; i <= k; i++){
        dp[0][i] = v[0];
    }
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= k; j++){
            if( j >= w[i] ) dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n-1][k] << endl;

dp 문제다
i번째일 때 각 무게 마다 최댓값을 적어 놓으면 된다.
dp[i][무게] = max(dp[i-1][무게], dp[i-1][무게-i번째 물건의 무게] + i번째 물건의 가치
i번째 물건을 넣을지 말지를 비교해 줘야 하기 때문이다!!
</br>

---

쭉 쭉 갑시다
</br>