백준: Gold4 - 1351, 1477

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

1351: 무한 수열

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

A0 = 1, Ai = A[i/p] + A[i/q]일 때 An 구하기

long long func(long long i){
    if( !m.count(i) ){
        long long ip = i/p, iq = i/q;
        m.insert(make_pair(ip, func(ip)));
        m.insert(make_pair(iq, func(iq)));
        m.insert(make_pair(i, m[ip]+m[iq]));
    }
    return m[i];
}

이것도 처음엔 dp로 하면 되나~ 했는데 n의 범위가 10^12라서 그만한 크기 배열을 준비할 수 없겠더라.
그래서 그냥 맵에다가 넣고 재귀 식으로 했는데 잘 돌아간다.
</br>

1477: 휴게소 세우기

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

휴게소를 m개 더 지어서 가장 먼 거리가 최소가 되게 하기

처음에는 각 휴게소들의 거리를 우선순위 큐에 넣어서, 걔네를 쪼개 주면 풀릴 줄 알았는데 아니더라. 예제도 안 돌아 간다ㅋㅋ

ex)
6 7 800
622 411 201 555 755 82
답: 70

우선순위 큐로 하면??
0: 210 144 133 119 82 67 45
1: 144 133 119 105 105 82 67 45
2: 133 119 105 105 82 72 72 67 45
3: 119 105 105 82 72 72 67 67 66 45
4: 105 105 82 72 72 67 67 66 60 59 45
5: 105 82 72 72 67 67 66 60 59 53 52 45
6: 82 72 72 67 67 66 60 59 53 53 52 52 45
7: 72 72 67 67 66 60 59 53 53 52 52 45 41 41
답이 72로 나옴

    cin >> n >> m >> e;
    v.push_back(0);
    v.push_back(e);
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size()-1; i++){
        d.push_back(v[i+1] - v[i]);
    }
    int l = 0, h = e, ans = e;
    while( l < h-1 ){
        int mid = (l+h)/2;
        int cnt = 0;
        for(int i = 0; i < d.size(); i++){
            cnt += d[i]/mid;
            if( d[i] % mid == 0 ) cnt--;
        }
        if( cnt > m ) l = mid;
        else h = mid;
    }
    cout << h << endl;

그래서 알고리즘 분류라는 힌트를 봐 버렸다… 이분 탐색 문제라더라
따라서 이분 탐색으로 현재 거리 간격을 기준으로 m개가 지어지는지를 확인한다.
만약 m개보다 더 지어진다면, 현재 거리 간격이 너무 좁은 것이므로 l을 증가시키고, 아니면 h를 줄인다.
cnt가 m이 된다고 바로 종료하면 안 된다. 더 좁은 거리를 찾을 수도 있기 때문이다.
그리고 l과 h는 2 이상 차이 나야 한다. 그래야 mid가 l 또는 h가 되지 않기 때문에… 만약 그냥 l < h로 조건을 걸면 무한 루프를 돌게 될 수 있다.

ex)
6 7 800
622 411 201 555 755 82
답: 70

while 조건을 l < h로 할 경우
l   mid h   cnt
68  71  75  7   <- cnt가 m이지만 최소 아님
68  69  71  8
69  70  71  7
69  69  70  8
69  69  70  8
69  69  70  8
...

마지막으로, 답은 최댓값을 의미해야 하므로, h 쪽이 답이 되어야 한다.

ex) 0 98 100
답: 2

</br>

---

이분 탐색은 항상 은근히 까다로워
</br>