백준: Class 5 - 9527, 10775, 12015

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

9527: 1의 개수 세기

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

long long dp[54];

long long func(long long a){
    long long ret = a & 1;
    for(int i = 54; i > 0; i--){
        if( a & (1LL << i) ){
            ret += dp[i-1] + (a - (1LL << i) + 1);
            a -= 1LL << i;
        }
    }
    return ret;
}

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

    long long a, b;
    cin >> a >> b;

    dp[0] = 1;
    for(int i = 1; i < 54; i++){
        dp[i] = 2*dp[i-1] + (1LL << i);
    }

    cout << func(b) - func(a-1) << endl;
}

와~ 비트 연산이란…
dp 구하기는 했는데 그 뒤를 잘 모르겠어서 다른 분 풀이를 봤다
얘도 누적합 구해서 빼주는 거다. dp[i] = 2^i일 때 1의 개수 누적합
그래서 만약 11101101을 예로 하면

ex) 11101101
11101101 = 1101101 | 10000000
 1101101 =  101101 |  1000000
  101101 =    1101 |   100000
    1101 =     101 |     1000
     101 =       1 |      100

처럼 계산한다.
</br>

10775: 공항

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

struct UnionFind{
    vector<int> parent;
    UnionFind(int n) : parent(n+1){
        for(int i = 0; i < n+1; i++){
            parent[i] = i;
        }
    }
    int f(int u){
        if( u == parent[u] ) return u;
        return parent[u] = f(parent[u]);
    }
    void merg(int u, int v){
        u = f(u), v = f(v);
        parent[u] = v;
    }
};

// in main()
    for(int i = 0; i < p; i++){
        int a;
        cin >> a;
        int pa = uf.f(a);
        if( pa == 0 ) break;
        uf.merg(pa, pa-1);
        cnt++;
    }
    cout << cnt << endl;

그냥 그리디 하면 시간 초과 날 거 같은데 뭐지
이것도 union find를 사용하는 거라고 한다… 구별을 잘 못하겠네
채울 수 있는 만큼 큰 수로 채우기 때문에 그리디랑 복합된 거긴 하다.

0 1 2 3 4
0 1 2 3 4

4 도착
0 1 2 3 4
0 1 2 3 3

2 도착
0 1 2 3 4
0 1 1 3 3

2 도착
0 1 2 3 4
0 0 0 3 3

1 도착
0 1 2 3 4
0 0 0 3 3
1의 부모 == 0이므로 끝


만약 4가 도착하면
4의 부모: 3이므로 3과 2 merge
0 1 2 3 4
0 0 0 0 3

0 1 2 3 4
0 0 0 0 0
경로 압축

</br>

12015: 가장 긴 증가하는 부분 수열 2

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

    ind.push_back(nums[0]);
    for(int i = 1; i < n; i++){
        if( nums[i] > ind.back() ) ind.push_back(nums[i]);
        else{
            auto it = lower_bound(ind.begin(), ind.end(), nums[i]);
            *it = min(*it, nums[i]);
        }
    }

    cout << ind.size() << endl;

자꾸 시간 초과 나서 찾아 봤는데, 알고리즘은 생각한 게 맞았는데 이분 탐색 구현을 잘못한 것 같다 난 이분 탐색을 잘 못하나 봐…
lower bound 저거 쓰니 편하니 좋네

아무튼 전에 비슷한 문제 풀었었는데,

dp[i] = i번째 수에서 가능한 가장 긴 수열의 크기

따라서 i-1번째까지 다 검색해서 가능하면 +1 함.

얘는 n이 짱 커서 그렇게 풀면 시간 초과 난다
그래서,

ex) 10 20 30 9 21 50

ind: 10
ind: 10 20
ind: 10 20 30
ind:  9 20 30   < 10보다 9가 작으므로 바꿈
ind:  9 20 21   < 30보다 21이 작으므로 바꿈
ind:  9 20 21 50

이렇게 수열의 크기를 인덱스로 하고, 그 값은 가능한 값들 중 가장 작은 녀석으로 저장했다
지금 보니 어차피 작은 애들끼리 얘기라 안 바꿔도 될 거 같기도 하네
</br>

---

열심히…
</br>